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 are
No 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 are
Have 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 array
The 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 are
No 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 are
No repeat
, an array of positive integers that can be repeatedly evaluated and takenArrangement of different
The 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 tree
Start-end
Node,; - 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 45
The value of 135 from the right boot
The 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