Front-end Data Structures and Algorithms (XIV) : 01 The Art of Execution – Backtracking Algorithms (II)

01 The Art of Execution – Backtracking Algorithms (PART 1)

preface

The last chapter introduced recursion and backtracking step by step. I believe I have had a preliminary understanding of backtracking. The next chapter mainly introduces more topics related to backtracking to deepen our understanding of it in breadth.

Permutation problem

46 – All of them

Given a sequence without repeating digits, return all possible permutations. Example: Input: [1, 2, 3] Output: 31 [[1, 2, 3], [1], [2,1,3],,3,1 [2], [3,1,2], [3, 2, 1]] source: the power button (LeetCode) link: https://leetcode-cn.com/problems/permutationsCopy the code

This problem is similar to the previous combination problem, but can be broken down into a tree problem. Let’s look at the diagram first:

The difference between this permutation problem and the combinatorial problem is that every time we iterate we have to go from the beginning of the sequence of numbers, and when we go to the next level of recursion, we have to tell the next level that I’ve been visited. For example, if we look at the first subtree on the left, when 1 is accessed, we can only access 2 and 3 when we go to the next level of recursion, and when we go to 2, we can only access 3 when we go to the next level.

Using the framework of write composition traceback, 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
};
Copy the code

The result is this:

,1,2,1,1 [[1], [1],,1,3 [1], [1, 2, 1],,2,2 [1], [1, 2, 3],,3,1 [1], [31] 1, filling [1], [2,1,1],,1,2 [2], [2,1,3], [2, 2, 1], [2,2,2]. 2,3,1 [2, 2, 3], [], [31] 2, filling [2], [3,1,1],,1,2 [3], [3,1,3], [3, 2, 1], [3,2,2], [3, 2, 3], [3,3,1], [31] 3, filling [3]]Copy the code

All permutations are printed out, a completely unlimited tree of execution. You need to put restrictions on nodes that have already been visited so that the next level of recursion cannot access them, and it would be too slow to iterate through the current permutation each time to see if there is an element that is currently being visited. We add an used array to mark the elements that have already been accessed. The change code is 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]) {// Used [I] = true Arr. Push (nums[I]) // Add the current element to the array. _helper(arr) used[I] = false Revalue to false arr.pop() // and pop it}}} _helper([]) return ret};Copy the code

The execution sequence of this code is very clever, you can see the debugger step by step.

Subset problem

78 – a subset

Given an array of integers with no repeating elements, nums returns 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: the power button (LeetCode) link: https://leetcode-cn.com/problems/subsetsCopy the code

Similar to the composition problem, except that you need to print out the entire tree of nodes, the empty array is a subset of each array. Again, we use backtracking to traverse a tree first, and then move the starting position one bit back as we traverse the next subtree, because each node must be a subset of the original array, and the largest subset is itself, so there is no restriction.

The code is as follows:

Var subsets = function (nums) {const ret = [] const _helper = (start, arr) => {ret.push([...arr]); Each node is a subset for (let I = start; i < nums.length; I ++) {arr.push(nums[I]) _helper(I + 1, arr) // I + 1 recursion does not visit smaller node values arr.pop()}} _helper(0, []) return ret};Copy the code

Segmentation problem

93 – Recover the IP address

Given a string containing only numbers, undo it and return all possible IP address formats. A valid IP address consists of four integers (each integer is between 0 and 255, and cannot contain a leading 0), separated by a hyphen (.). Input: s = "25525511135" Output: ["255.255.11.135","255.255.111.35"] https://leetcode-cn.com/problems/restore-ip-addressesCopy the code

This is a new genre. Be more specific. The segmentation process still uses backtracking. When the splicing of an address does not match the IP address, we can try another possibility. However, this splicing has two significant rules, which can also be used as the end condition of our recursion:

1. There can be a maximum of three digits between each decimal point, and their value cannot be greater than 255.
2. You can only use three decimal points in total, and if you don’t have a valid one after thatIPThen you can’t spell it out.

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

The recursive tree is too large, all give up, for the moment to see on the left side of the tree, thinking it is, according to a tree on the left side of the first to try a interception, when does not meet the backs up a tree for the two layer of interception, enclosed gradually expand the scope of the interception to try and use 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) {// if (start === s.length) {// and cut to the last ret.push(IP) // find the valid IP} return} for (let I = 1;  i < 4; If (val <= 255) {if (val <= 255) {if (val <= 255) {if (val <= 255) {if (val <= 255) { Otherwise filter _helper(dot-1, start + I, IP + val + (dot === 1? }} _helper(4, 0, ") return ret};}} _helper(4, 0, ") return ret};Copy the code

Initialize three variables, dot represents the remaining decimal point, one for each level of recursion, ending recursion when 0; The second variable, start, is used to indicate the current position of the truncated string. A valid IP is found only when the last digit is truncated and there is no decimal point. The third is an empty string that initializes the IP address used for concatenation.

Recursive trees are huge, but you can’t use more than three decimal points, so this tree has at most four levels; The rule is that each layer can only truncate a maximum of three characters, so each node can have a maximum of three children. Analyze a pass, submit code:

Missing the case combination of 0x or 0xx boundary, such combination must be illegal, let’s draw a recursion tree for this special case to see what it is:

Add boundary case handling to the for loop:

for (let i = 1; i < 4; i++) { if (i ! == 1 &&s [start] === "0") {// If (break == 1 &&s [start] === "0") {// If (break == 1 &&s [start] === "0") { } const val = +s.slice(start, start + i); if (val <= 255) { _helper(start + i, dot - 1, ip + val + (dot === 1 ? "" :". ")); }}Copy the code

At this point, you can pass, do you think that’s all? Of course, it’s not so simple, if the interview encountered this topic, the final pass can only be a pass. This problem is mainly to investigate the pruning problem in backtracking, which algorithm can be optimized. The recursive termination condition is not only the first two, but also one:

3. The character length to be cut must be within4to12Bit between, otherwise can’t split out of the legalIP.

This condition also applies to partitioned characters, and with this recursive termination condition, our previous recursion tree can terminate prematurely at the first step. The entire string is 25525511135, which is separated by character 2 after a decimal point. The remaining 5525511135 is longer than the decimal point *3, so it is impossible to separate the legal address. This is the part that can be pruned. If start + I > s.length, you can prune it.

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; } the if (s.l ength - start < dot | | s.l ength - start > 3 * dot) {/ / pruning return; } for (let i = 1; i < 4; I ++) {if (start + I > s.length) {// 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; };Copy the code

FloodFill dyeing problem

200 – Number of islands

Given a two-dimensional grid of '1' (land) and '0' (water), count the number of islands in the grid. Islands are always surrounded by water, and each island can only be formed by connecting adjacent lands horizontally and/or vertically. Furthermore, you can assume that all four sides of the grid are surrounded by water. Input: the grid = [[" 1 ", "1", "0" and "0" and "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 "and" 0 ", "1", "0" and "0"], [" 0 "and" 0 ", "0", "1", "1"]] output: three sources: LeetCode link: https://leetcode-cn.com/problems/number-of-islandsCopy the code

A classic DFS and BFS problem, finding all the islands in a two-dimensional matrix, is a bit more difficult to find in the matrix. Why is it called a dyeing problem? We can assume that the number one in the matrix is a groove, and when the pigment is poured into one of the nodes, its grooves, up, down, left and right will be diffused in the same way.

Staining starts with a node, then spreads it up, down, left and right, and then stains its surrounding nodes with the same rules, which is the same problem.

So our idea is to need a recursive function, its role is to spread point is set to 0, said the node has been dyed, then it’s up and down or so the execution of the same recursive logic, until the end of the starting point of the recursive call, then all connected 1 will be set to 0, all also said find a piece of islands, island number + 1. Depth-first staining diagram is as follows:

The problem seems to be complicated, but in fact the code logic is clearer and easier to understand than the previous backtracking questions. The code is as follows:

Var numIslands = function (grid) {const m = grid[0].length // let res = 0 const DFS = (I, j) = > {the if (I < 0 | | j < 0 | | I > = m | | j > = n) {/ / if crossing the line, If (grid[I][j] === '0') {if (grid[I][j] === '0') {if (grid[I][j] === '0') {if (grid[I][j] === '0') { J) // upper DFS (I, j + 1) // right DFS (I + 1, j) // lower} for (let I = 0; i < m; i++) { for (let j = 0; j < n; J++) {/ / ergodic matrix of each point if (grid [I] [j] = = = '1') {/ / meet 1 DFS started depth first search (I, j) res++}}} return res}Copy the code

The board problem

51-N Queen

The n Queens problem is the study of how to place n queens on an n by n board so that queens cannot attack each other. Given an integer n, return all the different solutions to the n-queen problem. Each solution contains an explicit chess placement scheme for the n-queen problem, in which 'Q' and '.' represent queens and slots, respectively. Input: 4 output: [[. "q..", / / solution 1... "Q", "Q...", ".. Q. "], [".. Q. ", / / solution 2 "Q...", "... Q ", ". Q.. "]] source: the power button (LeetCode) link: https://leetcode-cn.com/problems/n-queensCopy the code

The famous queen n question, at its best, can be a chapter in its own right. Given an N by N board, how many ways can n queens, who cannot attack each other, be placed?

It seems that the problem is to find the solution in a checkerboard, but in fact it is also a tree problem. The number of nodes in each layer is the size of the checkerboard. As for the position of the next line, it needs to be determined according to the position of the previous queen, so as to have the operation of pruning.

Let’s take the smallest checkerboard 4 * 4 with a solution as an example. The problem can be abstractly understood as trying to place the queen in each square in the first row, and then how it can be placed. This is the process of violence backtracking. After placing a queen in each row, her attack range needs to be marked on the board, and the queen in the next row cannot be placed in the attack range of the previous queen. The following shows how 4 * 4 finds 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 row and column is easy to know, the difficulty lies in how to confirm the attack range of the two diagonal lines, in fact, there is a rule, we mark the coordinate of the row and column of the board on the board can be found:

In an n by n chessboard, there must be 2n minus 1 diagonals, and the state of whether the two diagonals are in range of attack can be stored in two arrays. Right to left diagonals in the array are row + column, and left to right diagonals in the array are row – column + n – 1, just to make it easy to count from array 0.

So every time you place a queen in a row, you need to record her attack range. When you place a queen later, you need to meet two conditions: not in the same column as all the queens before you, and not within the attack range of all the queens before you on two diagonal lines. If there is no place to put at the end of the search, it is necessary to go back to other empty places and restore the status value set for this place. The code is as follows:

var solveNQueens = function (n) { const res = []; // Place all checkerboards const col = []; // Initialize column state const dia1 = []; // Initialize the diagonal state from right to left const dia2 = []; // Initialize diagonal state from left to right const _helper = (rowIdx, row) => {if (rowIdx === n) {// When the last row is placed, a checkerboard res.push(generateBoard(row)) is found;  // Generate a new checkerboard return; } for (let colIdx = 0; colIdx < n; colIdx++) { if ( ! Col [colIdx] && // Column out of range! Dia1 [rowIdx + colIdx] && // Right to left diagonal is not under attack! Dia2 [rowidx-colidx + n-1] // Left to right diagonal not in attack state) {row.push(colIdx); Col [colIdx] = true; Dia1 [rowIdx + colIdx] = true; // Set the diagonal attack range dia2[rowidx-colidx + n-1] = true; _helper(rowIdx + 1, row); Col [colIdx] = false; Dia1 [rowIdx + colIdx] = false; 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 an n * n and both. 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 a character format} return checkerboard; }; _helper(0, []); // Place return res from line 0; };Copy the code

The last

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 backtracking algorithm. The above are only a few representative problems. These problems all have one thing in common: it takes violence enumeration to find all the solutions, and the problem can be broken down into tree problems.