Brush these 15 tracebacks, and you're ready for a no-brainer assault interview

preface

Backtracking, is no brain rush, after hitting a wall to take a step back to continue, belongs to a violent way of thinking;

In fact, it is also the same, when we encounter some classification discussion problems, we can not think of a more sophisticated solution, the first thing we consider is violence enumerate all the cases, and then deal with, and backtracking is such a violent method

The next TAB is going to be a general sorting algorithm

Drainage of the

Brush these two pointer questions, you can tear the front end of the interview

After brushing the 12 sliding Windows, you can tear the front end of the interview

Brush these 20 dichotomy questions, may still tear the big factory interview

Brush these a few pile of questions, or may not tear the big factory interview

Brush these 30 tree questions, may still tear the big factory interview

Brush these 20 linked list questions, may still tear the big factory interview

Brush these 15 DP questions, can only chance the topic into dachang

Brush up on these bits, and wait until you consider the job interview

The body of the

In the process of doing backtracking problems, I will find myself confused, because many questions seem not to need to go back. In the process of implementing the next step, I will make a decision and then contain the possible failure. At this time, generally, the operation that can continue to go down is ok, we can actually call this method pruning

I once with meditation, isn’t back is useless, isn’t it as long as the brain to a line still, pruning is actually good, going back what, until the core idea of back, it is a kind of violent solution, that is if you can use other ways, need not back, actually is a good way of thinking, in general, the complexity of the back will be high

So when do you use backtracking? That you can’t predetermine the outcome, or that your choices are not just related to the choices of the adjacent layers, but to the deeper layers, like 51.n Queen

What we need is a complete board. The choices of each layer will affect the layout of the whole board. It is difficult to figure out all possible situations at the moment of playing chess, so backtracking is a good choice

And for some only with the upper impact, this time pruning is also a good choice;

In fact, when making a series of summaries, we will try our best to use a series of methods to solve the problem, but we also pursue multiple solutions to one problem, and what we finally want to achieve is not limited to a certain writing method, but as long as we see, we can a out;

So try to review most of the conventional TAB again, and then slowly fill, summarize their own solution scheme, is the purpose of summary it;

Let’s work together

Topic summary

arrangement

46. The whole arrangement
47. Full permutation II

combination

39. Sum of combinations
40. Sum of combinations II
216. Sum of combinations III
377. Sum of combinations ⅳ

A subset of

78. The subset
90. The subset II

cutting

131. Split palindrome strings
93. Restore the IP address

The path

112. Sum of paths
113. Sum of paths II
437. Sum of paths III

N queen

51. The N queens
52. Queen II

Answer key

46. The whole arrangement

Analysis of the

There are no duplicate numbers, so you need to count all permutations, so you know what values you’ve gotten during the enumeration process
Cache two arrays arR during enumeration,getIndex, arr is the array in enumeration,getIndex is the passed value state, if the current ARR passed the corresponding subscript value is 1, not passed is 0
When adding values to the temporary array ARR at each level, you need to ensure that the values will not be added repeatedly. You can iterate over the ARR at each encounter. Since the values are unique, it is ok.
In this case, space for time, using getIndex to cache the corresponding state, the complexity of each lookup is O(1){O(1)}O(1).
The time complexity is O(n2){O(n^2)}O(n2), the space complexity is O(n){O(n)}O(n).


var permute = function (nums) {
  let ret = [];

  const dfs = (arr, getIndex) = > {
    if (arr.length === nums.length) {
      ret.push(arr);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      const num = nums[i];
      if(!!!!! getIndex[i])continue; // If it exists, the value already exists
      getIndex[i] = 1;
      dfs([...arr, num], getIndex);
      getIndex[i] = 0; }};const getIndexArr = new Array(nums.length)
  dfs([], getIndexArr);
  return ret;
};

Copy the code

47. Full permutation II

Analysis of the

Since this time contains duplicate numbers, and cannot have duplicate values, so you can consider sorting first
(1) Caches two arrays with duplicate values. (2) Caches two arrays with duplicate values. (3) Caches two arrays with duplicate values
The difference is that each time you go back, you need to judge whether the next value is the same as the current value. If it is, you need to skip it to avoid repeated permutations
Time complexity O(n2){O(n^2)}O(n2), space complexity O(n){O(n)}O(n)


var permuteUnique = function(nums) {
    const ret = []
    const len = nums.length
    nums.sort((a,b) = >a-b) / / sorting
    const dfs = (arr,indexArr) = > {
        if(arr.length === len ){
            ret.push(arr)
            return 
        }
        for(let i = 0; i<len; i++){if(!!!!! indexArr[i])continue
            const num = nums[i]
            indexArr[i] = 1
            dfs([...arr,num],indexArr)
            indexArr[i] = 0
            // If the next value is the same, it is time to repeat the same path, so skip it
            while(nums[i+1]=== nums[i]) {
                i++
            }
        }
    }
    dfs([],[])
    return ret
}

console.log(permuteUnique([1.1.2]))
Copy the code

39. Sum of combinations

Analysis of the

Candidates areNo repeat, array of positive integers
The value can be repeated, but cannot be taken backwards because it has nothing to do with the permutation. Therefore, an initial subscript value needs to be maintained. Contrast with [combinatorial sum IV]

 var combinationSum = function(candidates, target) {
    const ret = []

    const dfs = (start,arr,sum) = > {
        if(sum === target){
            ret.push(arr)
            return 
        }
        if(sum>target) return 

        for(leti = start; i<candidates.length; i++){// Since repeated fetches are allowed, each fetches start from the start node
            dfs(i,[...arr,candidates[i]],sum+candidates[i])
        }
    }

    dfs(0[],0)
    return ret
}
Copy the code

40. Sum of combinations II

Analysis of the

Candidates areHave any repeat, array of positive integers
Each value in an array can be fetched only once; The value cannot be repeated, but the value can be repeated: [1,1,2,3] -> [1,1,2],[1,3] -> 4
In order not to get duplicate values, you have to skip the same values, and that’s when you need to check the arrayThe sorting
At each level of enumeration, when a duplicate value occurs in the loop, cut the enumeration for that part of the loop, because there must be the same part
The subscript of the first DFS input parameter is +1, indicating that the last value cannot be repeated

 var combinationSum2 = function (candidates, target) {
    candidates.sort((a,b) = >a-b)
    const ret= []

    const dfs = (start,arr,sum) = > {
        if(sum === target) {
            ret.push(arr)
            return 
        }
        if(sum>target || start>= candidates.length) return 
        for(leti = start; i<candidates.length; i++){// Cut out the duplicate
            if(i > start && candidates[i] === candidates[i-1]) continue
            // Start is the subscript to start the enumeration, but the value inserted into the temporary array is the current subscript
            dfs(i+1,[...arr,candidates[i]],sum+candidates[i])
        }
    }
    dfs(0[],0)
    return ret
}
Copy the code

216. Sum of combinations III

Analysis of the

Given is not a concrete array, but a length limit k, and a target value target — the same as the candidates areNo repeat, an array of positive integers from 1 to 9
Therefore, it can be regarded as a special case of the combined sum of 39, but the judgment conditions are different

var combinationSum3 = function (k, n) {
  const ret = [];

  const dfs = (start, arr, sum) = > {
    if (arr.length === k && sum === n) {
      ret.push(arr);
      return;
    }
    if (arr.length > k || sum > n) {
      return;
    }

    for (let i = start + 1; i < 10; i++) { dfs(i, [...arr, i], sum + i); }}; dfs(0[],0);
  return ret
};
Copy the code

377. Sum of combinations ⅳ

Analysis — backtracking

Candidates areNo repeat, an array of positive integers that can be repeatedly evaluated and takenArrangement of differentThe combination of
So this is a lot like the sum of combinations, except they’re looking for permutations, whereas problem 1 is looking for combinations that are not repeated
So there is no need to restrict the subscript of the combinatorial start enumeration, just start at 0 each time
And then I ran out of time

* /

var combinationSum4 = function (nums, target) {
  let ret = 0;
  const dfs = (sum) = > {
    if (sum === target) {
      ret++;
      return;
    }
    if (sum > target) return;
    for (let i = 0; i < nums.length; i++) { dfs(sum + nums[i]); }}; dfs(0);
  return ret;
};
Copy the code

Analysis – dp

Dp [I] represents the number of combinations that exist when the value is I
State transition equation dp[I] = sum(DP [i-NUMs [k]])
base case dp[0] = 1

var combinationSum4 = function (nums, target) {
    const dp = new Array(target+1)
    dp[0] =1  // If I happen to get a value of 0, then I get a value of 1
    for(let i = 1; i<target+1; i++){ dp[i] =0
        for(let j =0; j<nums.length; j++){if(i>=nums[j]){
                dp[i]+=dp[i-nums[j]]
            }
        }
    }
    return dp[target]
}
Copy the code

78. The subset

Analyze — find patterns

The array elements are different, and the return value does not contain duplicate subsets, that is, regardless of positional arrangement
Since it is not permutation dependent, we only need to iterate through numS once. Any value obtained without iterating through numS can be combined with the existing RET to form a new array, and then with the old item to form a new enumerated array
Time complexity O(n2){O(n^2)}O(n2)

 var subsets = function (nums) {
    let ret = [[]]
    for(let num of nums ){
        ret = [...ret,...ret.map(item= > item.concat(num))]
    }
    return ret
}
Copy the code

Analysis — Iterative backtracking

Enumerating all cases iteratively is no different from traversing a multi-fork tree
Time complexity O(N2){O(N^2)}O(N2)

var subsets = function (nums) {
    const ret = []
    const dfs = (start,arr) = > {
        ret.push(arr)
        if(arr.length === nums.length || start=== arr.length) return 
        for(leti = start; i<nums.length; i++){ dfs(i+1,[...arr,nums[i]])
        }
    }
    dfs(0[]),return ret
}
Copy the code

90. The subset II

Analysis – has duplicate values

In contrast to 78. Subset, there are more duplicate values, and duplicate values are not allowed in the returned array, so it is obvious to sort first
Then, in the backtracking process, if the value of the next iteration is the same as the current value, it is skipped to achieve the effect of de-duplication

var subsetsWithDup = function (nums) {
    nums.sort((a,b) = > a-b)
    const ret = []
    const dfs = (start,arr) = > {
        ret.push(arr)
        if(start === nums.length ) return // start exceeds the subscript, which is the maximum subscript value
        for(leti = start; i<nums.length; i++){ dfs(i+1,[...arr,nums[i]])
            while(nums[i] === nums[i+1]){
                i++ / / to heavy
            }
        }
    }
    dfs(0[]),return ret
}
Copy the code

131. Split palindrome strings

Analysis of the

It’s a combination of variants, because the order is already set and you just cut it
So in the traversal process, only when meet the palindrome requirements of the substring, can be cut, and then go down, otherwise it is better to cut
The determination of the substring can be easily realized by using the left and right double Pointers

var partition = function(s) {
    const ret = []
    // Determine if it is a string of primitives
    function isValid(s) {
        if(s.length === 1) return true // Only one character
        let l = 0,r = s.length-1
        while(l<r){
            if(s[l] ! == s[r])return false
            l++
            r--
        }
        return true

    }
    const dfs = (start,arr) = > {
        if(start === s.length){
            ret.push(arr)
            return 
        }
       let temp =' '
        for(leti =start; i<s.length; i++){ temp+=s[i]if(isValid(temp)){
                dfs(i+1,[...arr,temp])
            }
        }
    }
    dfs(0[]),return ret
};
Copy the code

93. Restore the IP address

Analysis of the

This problem is similar to 131. Splitting palindromes
This is also a shred string, except that the criteria has become that each segment must match a valid IP address, but the shelf is the same
There’s a lot of criteria here, and you just add the ones that meet the criteria, and you can cut off a lot of branches


var restoreIpAddresses = function (s) {
  const ret = [];

  function isValid(s) {
    if (s.length > 1 && s[0] = =0) return false; // Cannot start with 0
    if (s >= 1 << 8) return false; // must be between [0,255]
    return true;
  }

  const dfs = (start, arr) = > {
    if (arr.length === 4&& start ! == s.length)return; // It is already divided into 4 points, but not finished yet
    if (start === s.length) {
      if (arr.length === 4) {
        ret.push(arr.join("."));
      }
      // Whether divided into four parts or not, all left
      return;
    }

    let str = "";
    for (let i = start; i < s.length && i < start + 3; i++) {
      str += s[i];
      if (isValid(str)) {
        dfs(i + 1, [...arr, str]); }}}; dfs(0[]);return ret;
};

Copy the code

112. Sum of paths

Analysis of the

The path is the sum of the entire root-leaf route as target
DFS order traversal can go
Time complexity O(n){O(n)}O(n)

 var hasPathSum = function(root, targetSum) {
    let ret = false
    const dfs = (root,sum) = > {
        if(ret || ! root)return  // As long as one road is cleared, there is no other need to go
        sum += root.val
        if(! root.left && ! root.right && sum === targetSum) { ret =true
                return 
        }
        if(root.left) dfs(root.left,sum)
        if(root.right) dfs(root.right,sum)
    }
    dfs(root,0)
    return ret
};
Copy the code

113. Sum of paths II

Analysis of the

Again, I’m going to find the root-leaf path, but this time I’m going to save all the paths that I find that meet the requirements
Time complexity O(n){O(n)}O(n)

 var pathSum = function(root, targetSum) {
    const ret = []
    const dfs = (root,arr,sum) = > {
        if(! root)return 
        sum+=root.val
        arr = [...arr,root.val]
        if(! root.left && ! root.right && sum == targetSum){ ret.push(arr) }if(root.left) dfs(root.left,[...arr],sum)
        if(root.right) dfs(root.right,[...arr],sum)
    }
    dfs(root,[],0)
    return ret
};
Copy the code

437. Sum of paths III

Analysis of the

I could find any path in the treeStart-endNode,;
But the path must be downward, that is, not a.lift-a-a.light, which is actually a constraint to ease the difficulty
So the same top-down traversal is fine, but when you find a path that meets your needs, you continue to traverse to the leaf node
And 112. The biggest difference between 113. Sum of paths II and 113.
There is no limit to the end point, so I can record once in the traversal process as long as the targetSum is met, all the way to the position of the leaf node, and there is no need to judge when the leaf node is reached
You don’t have to start at the root node, so you can start at any node, so you have to walk through the whole tree, and you can find a path;
Time complexity O(nlogn){O(nlogn)}O(nlogn)


var pathSum = function (root, targetSum) {
  let ret = 0;
  // This is DFS with any root node to find the path and
  const dfs = (root, sum) = > {
    if(! root)return;
    sum += root.val;
    if (sum === targetSum) ret++;
    if(! root.left && ! root.right)return; // The leaf node is finished
    if (root.left) dfs(root.left, sum);
    if (root.right) dfs(root.right, sum);
  };

  // This is a walk through the tree, and then continue down
  const outer = (root) = > {
    if(! root)return;
    dfs(root, 0);
    outer(root.left);
    outer(root.right);
  };
  outer(root);
  return ret;
};

Copy the code

51. The N queens

Reference: leetcode-cn.com/problems/n-…

Analysis — Directly to meet the requirements of the Chessboard

Row is the depth of tree recursion, column is the width of each layer, using backtracking method DFS traversal tree
The whole process requires three parts, traversing the tree by backtracking, finding the nodes that meet the requirements, chessboard[row][col], and converting the two-dimensional array that meets the requirements into the string array that meets the requirements
Time complexity O(n∗logn){O(n*logn)}O(n∗logn)

var solveNQueens = function (n) {
  const ret = [];
  // 1. N The queen actually went through the process -- backtrace the tree
  const dfs = (row, chessboard) = > {
    if (row === n) {
      // the leaf node is null
      // But chessboard is a two-dimensional array, you can't just push it, you need a deep copy
      ret.push(getStrChessboad(chessboard));
      return;
    }
    // Each line starts from 0-n-1, and then backtracks if it doesn't meet the requirement
    for (let col = 0; col < n; col++) {
      if (isValid(row, col, chessboard)) {
        Chessboard [row][col] : chessboard[row][col
        chessboard[row][col] = "Q";
        dfs(row + 1, chessboard);
        chessboard[row][col] = "."; // Go back}}};// Determine whether the current node meets the requirements of queen N -- note that [0,n-1] is counted from left to right
  function isValid(row, col, chessboard) {
    / / the same column
    for (let i = 0; i < row; i++) {
      if (chessboard[i][col] === "Q") {
        return false; }}// Incline 45 'from left to right
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (chessboard[i][j] === "Q") {
        return false; }}// Tilt 135 'from right to left
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (chessboard[i][j] === "Q") {
        return false; }}// If it is not the same column or left and right slashes, the requirement is met
    return true;
  }

  // Convert the N queen of a two-dimensional array to a one-dimensional array string form
  function getStrChessboad(chessboard) {
    const ret = [];
    chessboard.forEach((row) = > {
      let str = "";
      row.forEach((item) = > {
        str += item;
      });
      ret.push(str);
    });
    return ret;
  }

  const chessboard = new Array(n).fill([]).map(() = > new Array(n).fill("."));
  dfs(0, chessboard);
  return ret;
};
Copy the code

52. Queen II

Analysis of the

The problem is basically the same as 51.n queen, except that instead of finding the full N Queen scheme, you just need to know how many there are
So the third part of the transformation can be deleted directly, and then directly copied over

var totalNQueens = function (n) {
  let ret = 0;

  const dfs = (row, chessboard) = > {
    if (row === n) {
      ret++;
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isValid(row, col, chessboard)) {
        chessboard[row][col] = "Q";
        dfs(row + 1, chessboard);
        chessboard[row][col] = "."; }}function isValid(row, col, chessboard) {
      for (let i = 0; i < row; i++) {
        if (chessboard[i][col] === "Q") return false;
      }

      for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (chessboard[i][j] === "Q") return false;
      }

      for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] === "Q") return false;
      }
      return true; }};const chessboard = new Array(n).fill([]).map(() = > new Array(n).fill("."));
  dfs(0, chessboard);
  return ret;
};

Copy the code

@ analysis

It’s pretty easy to backtrack, but is there a better way to do this with the condition isValid
In the first problem we wanted to create an instance of queen N, so we needed an array, but now we don’t need a specific queen N, so we can show queen N in other forms instead of an array
Use the three binary bits col, DLR, DRL to represent the values on the column, starting from the left 45The value of 135 from the right bootThe value of the
Col here is easy to understand because the value of I in each row does not change when the row is evaluated
For the DLR, the binary bits are slanted, and only such values qualify as 45 ‘slanted; Similarly, the same is true for the DRL Q…… Q…… Q…… Q…… Q…..
so

var totalNQueens = function (n) {
  let ret = 0;
  const dfs = (r, col, dlr, drl) = > {
    if (r === n) {
      ret++;
      return;
    }
    for (let i = 0; i < n; i++) {
      // The current coordinate is converted to the corresponding value of the binary bit
      const _col = 1 << i;
      const _dlr = 1 << (r + i); I = 1 << (r+ I); I = 1 << (r+ I)
      const _drl = 1 << (n - i + r);
      if ((col & _col) || (dlr & _dlr) || (drl & _drl)) continue; // As long as one of them is true,
      dfs(r + 1, col | _col, dlr | _dlr, drl | _drl); }}; dfs(0.0.0.0);
  return ret;
};

Copy the code

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Brush these 15 tracebacks, and you’re ready for a no-brainer assault interview

preface

The body of the

Topic summary

arrangement

combination

A subset of

cutting

The path

N queen

Answer key

46. The whole arrangement

47. Full permutation II

39. Sum of combinations

40. Sum of combinations II

216. Sum of combinations III

377. Sum of combinations ⅳ

78. The subset

90. The subset II

131. Split palindrome strings

93. Restore the IP address

112. Sum of paths

113. Sum of paths II

437. Sum of paths III

51. The N queens

52. Queen II

Brush these 15 tracebacks, and you’re ready for a no-brainer assault interview

preface

The body of the

Topic summary

arrangement

combination

A subset of

cutting

The path

N queen

Answer key

46. The whole arrangement

47. Full permutation II

39. Sum of combinations

40. Sum of combinations II

216. Sum of combinations III

377. Sum of combinations ⅳ

78. The subset

90. The subset II

131. Split palindrome strings

93. Restore the IP address

112. Sum of paths

113. Sum of paths II

437. Sum of paths III

51. The N queens

52. Queen II

Related Posts

Koa source code analysis

Redux vs. React Context API

Angular has many ways of building components. Which one have you used?