concept

Wikipedia definition of backtracking algorithm:

Backtracking uses the idea of trial and error, which attempts to solve a problem step by step. In the process of step solution, when it tries to find that the existing step solution can not get an effective and correct solution, it will cancel the calculation of the previous step or even the previous steps, and then try to find the answer of the problem again through other possible step solution. Backtracking is usually done using the simplest recursive method, and two things can happen after repeated steps:

  • Finding a possible correct answer;
  • After all possible steps have been tried, the question is declared unanswered

Key words: depth-first, recursion, try all possibilities, rollback, traversal (violent solution)

Difference between backtracking and dynamic programming

Thing in common:

It is used to solve multi-stage decision making problems. The multi-stage decision problem is:

  • There are many steps to solving a problem;
  • There are multiple options for each step (stage).

Difference:

  • Dynamic programming only requires us to evaluate what the optimal solution is, not what the specific solution of the optimal solution is. It is therefore suitable for evaluating the effectiveness of a program;
  • Backtracking algorithm can search for all schemes (including the optimal solution of course), but in essence it is a traversal algorithm with high time complexity.

Related classical algorithm problems

Lu Xun said, algorithm learning, seven points to practice, three points to learn. Now let’s come to some common questions about Kangkang

The whole arrangement

leetcode 46:

Input: [1, 2, 3] output: [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]

Backtracking algorithm idea:Description:

  • Each node represents a different stage of solving the full permutation problem. These stages are reflected by the “different values” of the variables, which are called “states”.
  • The depth-first traversal process with “backtracking” is used. After “backtracking”, the state variable needs to be set to be the same as before. Therefore, in the process of returning to the node at the previous level, the last selection needs to be reversed, which is called “state reset”.
  • Depth-first traversal, with the help of system stack space, saves the required state variables. In coding, we only need to pay attention to the correct value of state variables when traversing the corresponding node. The specific approach is as follows:pathThe variable appends at the tail, and when you go back, you have to undo the last selection, also at the tail, sopathA variable is a stack;
  • Depth-first traversal uses “backtracking” to achieve the effect of using a state variable globally.

Using the programming method to get the full permutation, is in such a tree structure to complete the traversal, from the tree root node to the leaf node path is one of the full permutation. So, the last layer of the tree is the recursive termination condition.

Code implementation:

var permute = function(nums) {
  let len = nums.length, res= [];
  if(! len)return res;

  let used = []; // boolean[]
  let path = []; //number[]
  dfs(nums, len, 0, path, used, res);
  return res;

  function dfs(nums, len, depth, path, used, res){
      if(depth === len) {
          // Path is a dynamic array and cannot be pushed directly. You need to copy the current value to the result
          res.push([...path]); 
          return;
      }
      
      // All possible attempts are made at the depth position in the full array
      for(let i=0; i<len; i++){
          if(! used[i]){ path.push(nums[i]); used[i] =true;

              // Move down to the next position in the array
              dfs(nums, len, depth+1, path, used, res);

              // After forming a full array, go back and try other answers
              used[i] = false; path.pop(); }}}};Copy the code
  • First of all, except for the root node and the leaf node, every node in this tree does the same thing, that is, on the premise that some numbers have been selected, one number is selected from the remaining numbers that have not been selected, which is obviously a recursive structure.
  • Recursion terminates when enough numbers are selected in a permutation, so we need a variable to indicate the level at which the program recurses. We call this variabledepthOr let’s call itindex, indicates that the current full permutation is to determine the subscript isindexWhat is the number of theta;
  • Boolean arrayused, when initializedfalseIt means that these numbers have not been selected yet, and when we select a number, we set the corresponding position of the array totrueIn this way, when considering the next position, the time complexity of O(1) can determine whether the number has been selected. This is a kind of “space for time” idea.

These variables are called “state variables” and represent the stage at which a problem is solved. Appropriate state variables need to be designed for the problem scenario.

N queen

How does Leetcode 51 place n queens on an N by N board and keep queens from attacking each other

Input: 4 output: [[. “q..” that… “, “Q”, “Q., q.”], [“.. Q. “, “Q…”, “… Q “, “. Q.. “]]

  • Iterate over each column of each row. If the current position does not generate an attack, record the current position and end the loop of the row. If none of the rows can fit, or if you have completed all of the rows, you go back to the previous position and continue to see if the next position can fit, repeating.
  • So, the important thing is how do you know if the current position can fit, in a loop, you can only put one in a row, and then immediately go to the next row, so there are no duplicates in a row, what about the column and the diagonal? We use three arrays to record the use of columns and primary and secondary diagonals respectively. When a queen is placed at a location, the column is recorded in the column array. After that, the column cannot be used.
  • About the diagonal:

Primary diagonal rule: x-y=k (row-column = fixed value) Secondary diagonal rule: X +y= K (row + column = fixed value) So, when a queen is placed in a position, the value of the current row + column, and row-column value, subsequent positions if row + column or row-column duplicate the array, do not use.

Code implementation:

var solveNQueens = function(n) {
  if(n==0) return res;

  let col = [], main = [], sub = []; // boolean[]
  let res = []; // string[]
  let path = []; //number[]
  dfs(0, path);
  return res;

  function dfs(row, path){
      // depth-first traversal until the subscript n indicates that [0.. n-1] has been filled, and a result is obtained
      if(row == n){
          const board = convert2board(path);
          res.push(board);
          return;
      }

      // For each column with subscript row, try whether it can be placed
      for(let j=0; j<n; j++){
          if(! col[j] && ! main[row-j+n-1] && !sub[row+j]){
              path.push(j);

              // Record the attack range of this position
              col[j] = true;
              main[row-j+n-1] = true; // Add n-1 to prevent the array index from being negative
              sub[row+j] = true;

              // Go to the next line
              dfs(row+1, path);

              // Backtrack to remove the last value in path and try other options
              col[j] = false;
              main[row-j+n-1] = false; 
              sub[row+j] = false; path.pop(); }}}// Output a result
  function convert2board(path){
      let board = []; // string[]
      for(let i=0; i<path.length; i++){
          let ret = new Array(n).fill('. ');
          ret[path[i]] = 'Q';
          board.push(ret.join(' '))}returnboard; }};Copy the code

Backtracking algorithm problem template

Through the above problems, it is not difficult to find that the key point of backtracking algorithm is to define state variables well, continuously advance and reverse the state, try all possible solutions, and output the current scheme when the state is in the leaf node of the recursion tree.

// Simple template
function backtrack(){
  let res = [];
  let used = [];

  function dfs(depth, path){ // depth indicates the current phase
    // Recursive termination condition
    if(depth === len){
      res.push(path);
      return;
    }

    // Try all possible results against the current depth
    for(let i=0; i<len; i++){
      if(! used[i]){// This road is blocked
        path.push(nums[i]);
        used[i] = true;

        // depth+1 to go to the next stage
        dfs(depth+1, path);

        // Reset the status of this phase to try other possibilities of this phase
        used[i] = false; path.pop(); }}}}Copy the code