Following the book, the previous chapter made a progressive introduction from recursion to backtracking. I believe that I have a preliminary understanding of backtracking. Next, I will mainly introduce more topics related to backtracking, and deepen its understanding in breadth.

Given a sequence without repeated numbers, return all possible permutations. Example: Input: [1, 2, 3] Output: [ [1,2,3],[1,3,2],[2,1,3], [2,3,1],[3,1,2],[3,2,1] ] Source: LeetCode Link: https://leetcode-cn.com/problems/permutations

This problem is similar to the previous combined problem, but it can still be broken down into a tree problem. First look at the diagram:

The difference between solving the permutation problem and the combination problem is that we need to traverse from the beginning of the number sequence for each traversal, and when entering the next layer of recursion, we need to inform the next layer that it `我`

has been visited. For example, we look at the left side of a sub-tree, when `1`

after being accessed, entered under a layer of recursion can only access `2`

and `3`

the, when visited `2`

after entering the next level can only access `3`

the.

Using the framework of writing composite backtracking, we write the following code:

var permute = function (nums) { const ret = [] const/_helper = (arr) => { if (arr.length === nums.length) { ret.push([...arr]) return } for (let i = 0; i <nums.length; i++) { arr.push(nums[i]) /_helper(arr) arr.pop() } } /_helper([]) return ret };

The result is this:

[ [1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1 ,3,1], [1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2 ,2,2], [2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2],[3 ,1,3], [3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3] ]

Printed out all the permutations, an execution tree with no restrictions at all. It is necessary to add restrictions, so that the nodes that have been visited cannot be accessed at the next level recursively. If you traverse every time whether there is an element currently being accessed in the current arrangement, the efficiency is too slow. We add an `used`

array to mark the elements that have been visited. Change the code as follows:

var permute = function (nums) { const ret = [] const used = new Array(nums.length).fill(false) const/_helper = (arr) => { if (arr.length === nums.length) { ret.push([...arr]) return } for (let i = 0; i <nums.length; i++) { if (!used[i]) {//If the upper level has not been visited used[i] = true//mark has been visited and brought to the next layer arr.push(nums[i])//add the current element to the arrangement /_helper(arr) used[i] = false//This time the loop is executed, and the value is false again arr.pop()//and pop it } } } /_helper([]) return ret };

The execution sequence of this code is very clever, and everyone can take `debugger`

a step-by-step taste.

Given a set of integer arrays nums without repeated elements, return all possible subsets (power sets) of the array. Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] Source: LeetCode Link: https://leetcode-cn.com/problems/subsets

Similar to the combinatorial problem, but you need to print out the nodes of the entire execution tree, and the empty array is a subset of each array. Or use the backtracking method to first traverse a tree, and then move the starting position back by one when traversing the next subtree, because each node must be a subset of the original array, and the largest subset is also It is itself, so there are no restrictions.

code show as below:

var subsets = function (nums) { const ret = [] const/_helper = (start, arr) => { ret.push([...arr])//There are no restrictions, each node is a subset for (let i = start; i <nums.length; i++) { arr.push(nums[i]) /_helper(i + 1, arr)//i + 1 moves backward each time, and the subsequent recursion does not visit smaller node values arr.pop() } } /_helper(0, []) return ret };

Given a string containing only numbers, restore it and return all possible IP address formats. A valid IP address consists of exactly four integers (each integer is between 0 and 255, and cannot contain leading 0), Use'.' to separate integers. Input: s = "25525511135" Output: ["255.255.11.135","255.255.111.35"] Source: LeetCode Link: https://leetcode-cn.com/problems/restore-ip-addresses

This is a new type, to be more detailed. The process of segmentation still uses backtracking. When the splicing of a certain address does not match the `ip`

address, we can try another possibility. However, this splicing has two notable rules, which can also be used as the end condition of our recursion. :

- There can be at most three digits between each decimal point, and their value cannot be greater than 255.
- A total of only three decimal points can be used. If it is not legal after use
`IP`

, it will not be spelled out.

According to this idea, we try to draw a recursive execution diagram:

This recursive tree is too large. I will give up all the paintings. Let’s look at the tree on the left. The idea is to use the tree on the left to try to intercept one bit first. When it is not satisfied, it will fall back to the previous tree to intercept two bits. , And gradually expand the scope of interception to try, using these rules, we first write the first version of the code:

var restoreIpAddresses = function (s) { const ret = [] const/_helper = (dot, start, ip) => { if (dot === 0) {//run out of dots if (start === s.length) {//and intercept to the last digit ret.push(ip)//find a legal IP } return } for (let i = 1; i <4; i++) {//can only intercept three characters at most, so <4 const val = +s.slice(start, start + i)//intercept three child nodes if (val <= 255) {//Must be less than 255, otherwise filter /_helper(dot-1, start + i, ip + val + (dot === 1?'':'.')) //Recursively enter the next level, decimal point-1 //current position + 1 //If there is a decimal point, splice the decimal point, and finally splice an empty string } } } /_helper(4, 0,'') return ret };

Incoming three variables initialized, `dot`

representing the remainder of a decimal point, each using a recursion for `0`

the end of the recursion; a second variable `start`

, for indicating the current position of the character string taken, only the last one taken without a decimal point, to It is said that a legal one was found `IP`

; the third is an empty string, which is the initial `IP`

address for splicing .

Although the recursive tree is complicated, it can only use up to three decimal points, so this tree has at most `4`

layers; the rule is that each layer can only intercept up to three characters, so each node has at most three child nodes. Analyze one pass and submit the code:

The combination of cases where pairs `0x`

or `0xx`

boundaries are missing is handled, so the combination must be illegal. Let's draw a recursive tree for this special case to see what happens:

`for`

Add the processing of boundary conditions in the loop:

for (let i = 1; i <4; i++) { if (i !== 1 && s[start] === "0") {//As long as 0 has been used, it is illegal to join with any number break; } const val = +s.slice(start, start + i); if (val <= 255) { /_helper(start + i, dot-1, ip + val + (dot === 1? "": ".")); } }

At this point, you can pass it. Don’t you think that’s it? Of course it’s not that simple. If you encounter this question in the interview, you can only pass it. This question mainly examines the pruning problem in backtracking, and where the algorithm can be optimized. The recursive termination condition is not only the first two, but there is actually one more:

- Required character length must be taken
`4`

to`12`

between the position, or not valid division`IP`

.

This condition is also applicable to the characters after being split. With this recursive termination condition, our previous recursive tree can be terminated early in the first step. The entire string is `25525511135`

divided into characters after a decimal point `2`

, and the remaining `5525511135`

length is greater than the decimal point `\*`

3. It is no longer possible to split a legal address. This is the part that can be pruned. Another pruning operation is if you `start + i > s.length`

can pruning, the complete code is as follows:

const restoreIpAddresses = (s) => { if (s.length <4 || s.length> 12) { return []; } const ret = []; const/_helper = (start, dot, ip) => { if (dot === 0) { if (start === s.length) { ret.push(ip); } return; } if (s.length-start <dot || s.length-start> 3/* dot) {//pruning return; } for (let i = 1; i <4; i++) { if (start + i> s.length) {//pruning break; } if (i !== 1 && s[start] === "0") {//boundary break; } const val = +s.slice(start, start + i); if (val <= 255) { /_helper(start + i, dot-1, ip + val + (dot === 1? "": ".")); } } }; /_helper(0, 4, ""); return ret; };

Given a two-dimensional grid composed of '1' (land) and '0' (water), please count the number of islands in the grid. Islands are always surrounded by water, and each island can only be formed by connecting adjacent land in the horizontal and/or vertical direction. In addition, you can assume that all four sides of the grid are surrounded by water. Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3 Source: LeetCode Link: https://leetcode-cn.com/problems/number-of-islands

A classic `DFS`

sum `BFS`

problem is to find all the islands in a two-dimensional matrix. Finding on the matrix will be more troublesome. Why is it called the dyeing problem? We can assume that the matrix `1`

is a groove. When the paint is poured into one of the nodes, the grooves on the top, bottom, left, and right will be diffused and dyed.

Coloring starts with a node, then spreads its top, bottom, left, and right, and then uses the same rules to color the surrounding nodes. This is the same problem.

So our idea is to need a recursive function, its role is to set the diffusion point to `0`

indicate that the node has been dyed, and then perform the same recursive logic on the top, bottom, left, and right until the recursive call of the starting point ends, and then all connected the `1`

entire set will be `0`

, he said the island found a number of islands `+ 1`

can be. The depth-first coloring diagram is as follows:

This question seems complicated, but the code logic is clearer and easier to understand than the previous backtracking problem. The code is as follows:

var numIslands = function (grid) { const m = grid.length//column of matrix const n = grid[0].length//row of matrix let res = 0 const dfs = (i, j) => { if (i <0 || j <0 || i >= m || j >= n) {//If out of range, return return } if (grid[i][j] === '0') {//return when encountering water return } grid[i][j] = '0'//mark as colored dfs(i, j-1)//left dfs(i-1, j)//up dfs(i, j + 1)//right dfs(i + 1, j)//down } for (let i = 0; i <m; i++) { for (let j = 0; j <n; j++) {//traverse each point of the matrix if (grid[i][j] === '1') {//Depth first search starts when it encounters 1 dfs(i, j) res++ } } } return res }

The n queen problem studies how to place n queens on an n×n chessboard and make the queens unable to attack each other. Given an integer n, return solutions to all different n queen problems. Each solution contains a clear pawn placement plan for the n-queen problem, in which'Q' and'.' represent the queen and the empty position, respectively. Input: 4 Output: [ [".Q..",//Solution 1 "...Q", "Q...", "..Q."], ["..Q.",//Solution 2 "Q...", "...Q", ".Q.."] ] Source: LeetCode Link: https://leetcode-cn.com/problems/n-queens

The famous `n`

queen question, in detail, can be used as a separate chapter. Simply put, `(Queen)`

because the queen in chess can attack the horizontal line, vertical line, and two diagonal lines on `n/* n`

the board, ask you a chessboard, place `n`

a queen that cannot attack each other, and how many pendulums are there.放式。 Put the way.

It seems that the problem is to find a solution in a chessboard, but it is actually a tree-type problem. The number of nodes at each level is the size of the chessboard. As for the position where the next line can be placed, it needs to be determined according to the position of the previous queen, so there is pruning. Operation.

Let's take the smallest chessboard with a solution `4/* 4`

as an example. This problem can be understood abstractly as trying to place the queen in each square in the first row, and then how it can be placed. This is a violent backtracking search process. After placing a queen in each row, you need to mark her attack range on the chessboard, and the queen in the next row cannot be placed within the attack range of the previous queen. The following shows `4/* 4`

the process of finding one of the solutions:

How to quickly confirm whether the current point can be placed is the difficulty of this problem. The attack range of the row and column is easy to know. The difficulty lies in how to confirm the attack range of the two diagonal lines. In fact, this is also regular. The row and column coordinates can be found on the chessboard:

In a `n/* n`

chessboard, there must be `2n - 1`

a diagonal line. Whether the two diagonal lines are in the attack range can be stored in two arrays respectively. The subscript of the diagonal line from right to left is in the array, and the subscript of `行 + 列`

the diagonal line from left to right in the array is `行 - 列 + n - 1`

, for the convenience of `0`

starting statistics from the array .

So every time a queen is placed in a row, her attack range needs to be recorded. When placing the queen afterwards, two conditions need to be met: it cannot be in the same column as all the previous queens, and it cannot be in the same row as all previous queens. Within the attack range of two diagonals. If there is no place to put it at the end of the search, you need to go back to the other empty positions before to try, and restore the state value set for this place. code show as below:

var solveNQueens = function (n) { const res = [];//place all chessboards const col = [];//initialize the state of the column const dia1 = [];//Initialize the diagonal state from right to left const dia2 = [];//Initialize the diagonal state from left to right const/_helper = (rowIdx, row) => { if (rowIdx === n) {//After placing the last line, a chessboard was found res.push(generateBoard(row));//Generate a new board and return return; } for (let colIdx = 0; colIdx <n; colIdx++) { if ( !col[colIdx] &&//The column is not in the attack range !dia1[rowIdx + colIdx] &&//The diagonal line from right to left is not in attack state !dia2[rowIdx-colIdx + n-1]//The diagonal line from left to right is not in attack state ) { row.push(colIdx);//Put the matching column coordinates into the collection col[colIdx] = true;//Set the attack range of the column dia1[rowIdx + colIdx] = true;//Set the diagonal attack range dia2[rowIdx-colIdx + n-1] = true; /_helper(rowIdx + 1, row);//find the next row recursively col[colIdx] = false;//Reset the attack range of the column dia1[rowIdx + colIdx] = false;//reset the diagonal dia2[rowIdx-colIdx + n-1] = false; row.pop();//Pop up the last column coordinates } } }; const generateBoard = (row) => { const checkerboard = new Array(n) .fill() .map(() => new Array(n).fill("."));//Generate a chessboard with n/* n and all. for (let i = 0; i <n; i++) { checkerboard[i][row[i]] = "Q";//Set the corresponding column to Q checkerboard[i] = checkerboard[i].join("");//convert this line to character format } return checkerboard; }; /_helper(0, []);//place from line 0 return res; };

Through the study of these two chapters, it is not difficult to find that there are many types of problems that can be solved by the backtracking algorithm. The above is only a few representative topics. These problems have one thing in common: violent enumeration is needed to find all the solutions, and the problems can be disassembled into tree problems.

Reference: https://cloud.tencent.com/developer/article/1756818 Frontend Data Structure and Algorithm (14): 01 The Art of Execution-Backtracking Algorithm (Part 2)-Cloud + Community-Tencent Cloud