Front End Data Structure and Algorithm (14): 01 The Art of Execution-Backtracking Algorithm (Part 2)

Front End Data Structure and Algorithm (14): 01 The Art of Execution-Backtracking Algorithm (Part 2)

Preface

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.

Alignment problem

46-Full array

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 1after being accessed, entered under a layer of recursion can only access 2and 3the, when visited 2after entering the next level can only access 3the.

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 usedarray 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 debuggera step-by-step taste.

Subset problem

78-Subset

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

};

Segmentation problem

93-Recover IP address

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 ipaddress, we can try another possibility. However, this splicing has two notable rules, which can also be used as the end condition of our recursion. :

  1. There can be at most three digits between each decimal point, and their value cannot be greater than 255.
  2. 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, dotrepresenting the remainder of a decimal point, each using a recursion for 0the 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 IPaddress for splicing .

Although the recursive tree is complicated, it can only use up to three decimal points, so this tree has at most 4layers; 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 0xor 0xxboundaries are missing is handled, so the combination must be illegal. Let's draw a recursive tree for this special case to see what happens:

forAdd 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:

  1. Required character length must be taken 4to 12between 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 25525511135divided into characters after a decimal point 2, and the remaining 5525511135length 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.lengthcan 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;

};

floodFill staining problem

200-number of islands

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 DFSsum BFSproblem 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 1is 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 0indicate 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 1entire set will be 0, he said the island found a number of islands + 1can 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

}

Chessboard problem

51-N Queen

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 nqueen 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/* nthe board, ask you a chessboard, place na 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/* 4as 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/* 4the 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/* nchessboard, there must be 2n - 1a 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 0starting 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;

};

At 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 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