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

  1. There are no duplicate numbers, so you need to count all permutations, so you know what values you’ve gotten during the enumeration process
  2. 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
  3. 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.
  4. 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).
  5. 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

  1. Since this time contains duplicate numbers, and cannot have duplicate values, so you can consider sorting first
  2. (1) Caches two arrays with duplicate values. (2) Caches two arrays with duplicate values. (3) Caches two arrays with duplicate values
  3. 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
  4. 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

  1. Candidates areNo repeat, array of positive integers
  2. 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

  1. Candidates areHave any repeat, array of positive integers
  2. 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
  3. 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
  4. 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
  5. 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

  1. 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
  2. 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

  1. Candidates areNo repeat, an array of positive integers that can be repeatedly evaluated and takenArrangement of differentThe combination of
  2. 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
  3. So there is no need to restrict the subscript of the combinatorial start enumeration, just start at 0 each time
  4. 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

  1. Dp [I] represents the number of combinations that exist when the value is I
  2. State transition equation dp[I] = sum(DP [i-NUMs [k]])
  3. 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

  1. The array elements are different, and the return value does not contain duplicate subsets, that is, regardless of positional arrangement
  2. 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
  3. 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

  1. Enumerating all cases iteratively is no different from traversing a multi-fork tree
  2. 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

  1. 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
  2. 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

  1. It’s a combination of variants, because the order is already set and you just cut it
  2. 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
  3. 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

  1. This problem is similar to 131. Splitting palindromes
  2. 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
  3. 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

  1. The path is the sum of the entire root-leaf route as target
  2. DFS order traversal can go
  3. 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

  1. 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
  2. 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

  1. I could find any path in the treeStart-endNode,;
  2. But the path must be downward, that is, not a.lift-a-a.light, which is actually a constraint to ease the difficulty
  3. 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
  4. And 112. The biggest difference between 113. Sum of paths II and 113.
  5. 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
  6. 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;
  7. 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

  1. Row is the depth of tree recursion, column is the width of each layer, using backtracking method DFS traversal tree
  2. 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
  3. 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

  1. 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
  2. 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

  1. It’s pretty easy to backtrack, but is there a better way to do this with the condition isValid
  2. 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
  3. 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
  4. Col here is easy to understand because the value of I in each row does not change when the row is evaluated
  5. 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…..
  6. 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