1. Backtracking algorithm

1.1 What is backtracking?

Backtracking algorithm is actually a search attempt process similar to enumeration, which is mainly to find the solution of the problem in the search attempt process. When it is found that the solution condition is not met, it will “backtrack” back and try another path. — From Baidu Encyclopedia

1.1 General Steps:

1. For the given problem, the solution space of the problem is defined, which contains at least one (optimal) solution of the problem.
2. The structure of the solution space is determined so that the whole solution space can be easily searched by backtracking.
3. The solution space is searched depth-first, and the pruning function is used to avoid invalid searches.

1.2 How to understand backtracking algorithm?

1. Construct solution space structure for the problem
2. DFS search is performed on the structure of solution space
3. Set up backtracking exit and prune point, reduce invalid search, save effective solution at exit.

1.3 Which problems are solved?

1. Combination problem: N numbers in accordance with certain rules to find the set of k numbers
2. Slicing problem: A string can be sliced in several ways according to certain rules
3. Subset problem: how many subsets of a set of N numbers are eligible
4. Permutation problem: N number permutation according to certain rules, there are several permutations
5. Checkerboard problems: N queen, solving sudoku and so on.

1.4 Recursion and backtracking

First, explain the understanding of recursion and Backtrack.

1.4.1 Recursive (Recursive)

The technique by which a program calls itself is called recursion. Recursion as an algorithm is widely used in programming languages. A procedure or function in the introduction to the definition or call their own, directly or indirectly, with a kind of method, it is usually the problem of a large complex layers into a similar to the original problem of smaller problems to solve, the recursion strategy only a small number of procedures can be required to describe the problem solving process of repeatedly calculation, greatly reduces the amount of program code. — From Baidu Encyclopedia

In general, in order to describe a state of the problem, one must use the state above that state; And if you want to describe the previous state, you have to use the previous state of the previous state… The way you define yourself in terms of yourself is recursion.

1.4.2. Back (Backtrack)

Backtracking algorithm is actually a search attempt process similar to enumeration, which is mainly to find the solution of the problem in the search attempt process. When it is found that the solution condition is not met, it will “backtrack” back and try another path. — From Baidu Encyclopedia

In this way of thinking, we need to identify clearly three factors: Options, Restraints, and conditions of Termination.

1.5. Difference between recursion and backtracking

Recursion is an algorithmic structure. Recursion occurs in subroutines in the form of directly or indirectly calling itself. The classic example is factorial, which is calculated as n! = n * (n – 1)! n! =n \times (n-1)! , basically as follows:

let fac = (n) = > {
    if(n == 1) {return n;
    }else{
      return (n*fac(n - 1)); }}Copy the code

Backtracking is an algorithmic idea that is implemented recursively. The process of backtracking is similar to the exhaustive method, but it has the function of “pruning”, that is, the process of self-judgment.

Second, Leetcode backtracking

2.1-22. Parenthesis generation

The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations.

Example 1:

Enter n =3Output:"((()))"."() () ()"."() () ()"."() () ()"."() () ()"]
Copy the code

Example 2:

Enter n =1Output:"()"]
Copy the code

Tip: 1 <= n <= 8

Thought analysis

1. The number of left parentheses is n at the beginning; When the left parenthesis (() is left, proceed with the selection;
2. Select the close parenthesis when there is more left than the open parenthesis; Keep recursively making choices
3. Exit: when the string to build is 2n, at this time the branch has been built, add option;

Draw a graph

The problem solving code

var generateParenthesis = function (n) {
    const res = [];
    const backTracing = (lRemain, rRemain, str) = > { // The number of left parentheses, STR is the currently constructed string
        if (str.length == 2 * n) { // String construction is complete
            res.push(str);           // Add the solution set
            return;                  // End the current recursive branch
        }
        if (lRemain > 0) {         // As long as the left parenthesis is left, you can select it and continue with the selection (recursion)
            backTracing(lRemain - 1, rRemain, str + "(");
        }
        if (lRemain < rRemain) {   // Select the right parenthesis if there is more left than left parenthesis
            backTracing(lRemain, rRemain - 1, str + ")"); // Then proceed with the selection (recursion)}}; backTracing(n, n,""); // Recursive entry, the remaining number is n, the initial string is an empty string
    return res;
};
Copy the code

2.2-46. All permutations

Given an array nums that does not contain duplicate digits, return all possible permutations. You can return the answers in any order.

Example 1:

Enter: nums = [1.2.3] Output: [[1.2.3], [1.3.2], [2.1.3], [2.3.1], [3.1.2], [3.2.1]]
Copy the code

Example 2:

Enter: nums = [0.1] Output: [[0.1], [1.0]]
Copy the code

Example 3:

Enter: nums = [1] Output: [[1]]
Copy the code

1 <= nums.length <= 6-10 <= nums[I] <= 10

Their thinking

1. Backtracking termination conditions: the path length and reach nums length;
2. Add the current value to the path, if the result already contains the path, do not add to the result, otherwise continue to select this option;

The problem solving code

/ * * *@param {number[]} nums
 * @return {number[][]}* /
var permute = function (nums) {
    if(! nums.length)return
    let res = []
    let backTrack = path= > {
        // If the length meets the condition, add the result
        if (path.length === nums.length) {
            res.push(path)
            return
        }
        nums.forEach(item= > {
            if (path.includes(item)) return // Does not contain duplicate numbers
            backTrack([...path, item]) // Add path, continue recursive selection
        });
    }
    backTrack([])
    return res
};

Copy the code

2.3-N Queen problem

The study is how to place n queens on an n by n chessboard so that queens cannot attack each other.

Given an integer n, return the number of different solutions to the queen of N problem. * * *

Rule of queen’s move

The queen’s way of walking is: can walk horizontally and diagonally, the number of grids is not limited. So asking queens not to attack each other is equivalent to asking no two queens to be on the same row, column, and slash.

The sample

Example 1:

Enter n =4Output:2
Copy the code

Explanation: As shown in the figure above, there are two different solutions to the four queens problem.

Example 2:

Enter n =1Output:1
Copy the code

Tip: 1 <= n <= 9

Their thinking

1. Define a test function to determine the current position, with constraints such as, not in a row, not in a column, not in a diagonal (45 degrees and 135 degrees)
2. Define checkerboard; Standard backtracking;

Backtracking is used by placing a queen in each row in turn, with each newly placed queen having no attacks on the already placed queen, i.e., the newly placed queen cannot be in the same column and on the same slash as any already placed queen. When NNN queens are all placed, a possible solution is found and the number of possible solutions is added to 111.

photo

The problem solving code

var totalNQueens = function (n) {
    let count = 0; // Total number of queens that can be placed
    let isValid = (row, col, board, n) = > {
        // It moves down one line at a time
        // Check whether the same column contains data
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') {
                return false}}// Check whether the 45 degree diagonal is included
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') {
                return false}}// Check whether the 135 degree diagonal contains
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; j--, i--) {
            if (board[i][j] === 'Q') {
                return false}}return true
    }

    let backTracing = (row, board) = > {
        // Go to the last row, count the number of times
        if (row === n) {
            count++;
            return
        }

        for (let x = 0; x < n; x++) {
            // Determine if this position is suitable for the queen
            if (isValid(row, x, board, n)) {
                board[row][x] = 'Q'; // Place the queen
                backTracing(row + 1, board); / / recursion
                board[row][x] = '. '; // Backtrace, undo the result of processing
            }
        }
    }
    backTracing(0, board)
    let board = [...Array(n)].map(v= > v = ([...Array(n)]).fill('. ')) / / board
    return count
};
Copy the code

2.4-78. Subsets

You are given an array of integers, nums, whose elements are different from each other. Returns all possible subsets (power sets) of this array.

The solution set cannot contain duplicate subsets. You can return the solution set in any order.

Example 1:

Enter: nums = [1.2.3] output: [[],[1], [2], [1.2], [3], [1.3], [2.3], [1.2.3]]
Copy the code

Example 2:

Enter: nums = [0] output: [[],[0]]
Copy the code

1 <= nums.length <= 10-10 <= nums[I] <= 10 all elements in nums are different

Their thinking

1. Enumerates all optional numbers; Join option;
2. Undoes the added option and adds the option to the result

The problem solving code

const subsets = (nums) = > {
    const res = [];
    const backTracing = (index, list) = > {
        res.push(list.slice());     // Add the solution set before calling the subrecursion
        for (let i = index; i < nums.length; i++) { // Enumerate all the optional numbers
            list.push(nums[i]);       // Select this number
            backTracing(i + 1, list);         // Continue recursion based on the number chosen
            list.pop();               // Undo the selection}}; backTracing(0[]);return res;
};
Copy the code

2.5-77. Combinations

Given two integers n and k, return all possible combinations of k numbers in the range [1, n].

You can return the answers in any order.

Example 1:

Enter n =4, k = 2Output: [[2.4],
  [3.4],
  [2.3],
  [1.2],
  [1.3],
  [1.4]]Copy the code

Example 2:

Enter n =1, k = 1Output: [[1]]
Copy the code

1 <= n <= 20 1 <= k <= n

Their thinking

1. Enumerates all optional numbers; Join option;
2. Undoes the added option and adds the option to the result
3. Pruning condition: The length of the option meets the condition;

The problem solving code

/ * * *@param {number} n
 * @param {number} k
 * @return {number[][]}* /
var combine = function (n, k) {
    let result = [];
    let backTracing = (start, path) = > {
        // If the selection is full, add it to the result set
        if (path.length == k) {
            result.push(path.slice());
            return;
        }
        // From the beginning digit to the end digit
        for (let i = start; i <= n; i++) {
            // Add to the selection list
            path.push(i);
            // Continue the deep search
            backTracing(i + 1, path);
            // Undo the selectionpath.pop(i); }}; backTracing(1[]);return result;
};
Copy the code

2.6-081. Allow repeated selection of combinations of elements

Given an array of positive integer candidates with no duplicate elements and a positive integer target, find all unique combinations of the candidates that can make the sum the target number.

The numbers in the candidates can be selected repeatedly without limit. Both combinations are unique if at least one of the selected numbers has a different number. For a given input, there are fewer than 150 unique combinations of guaranteed and targets.

Example 1:

Enter: candidates = [2.3.6.7], target = 7Output: [[7], [2.2.3]]
Copy the code

Example 2:

Enter: candidates = [2.3.5], target = 8Output: [[2.2.2.2], [2.3.3], [3.5]]
Copy the code

Example 3:

Enter: candidates = [2], target = 1Output: []Copy the code

Example 4:

Enter: candidates = [1], target = 1Output: [[1]]
Copy the code

Example 5:

Enter: candidates = [1], target = 2Output: [[1.1]]
Copy the code

Description: 1 <= candidates.length <= 30 1 <= candidates.length [I] <= 200 Each element of the candidate is unique. 1 <= target <= 500

Their thinking

1. Add the current element to the option, and pass the calculation result to the option, continue the recursion;
2. When an item is selected and greater than the target value, end the option until a matching option is found and added to the result;

The problem solving code

var combinationSum = function (candidates, target) {
    const result = [], visited = [];
    backTracing(0.0);
    return result;

    function backTracing(sum, cur) {
        if (target === sum) result.push(visited.slice());
        if (target <= sum) return;
        for (let i = cur; i < candidates.length; i++) {
            visited.push(candidates[i]); // Add it to the options
            backTracing(sum + candidates[i], i);// Select this option to continue the recursion
            visited.pop(); // Insert this selection}}};Copy the code

2.7-216. Sum of combinations III

Find all the combinations of k numbers that add up to n. Only positive integers from 1 to 9 are allowed in a combination, and there are no duplicate digits in each combination.

Note: All numbers are positive integers. The solution set cannot contain repeated combinations.

Example 1:

Enter k =3, n = 7Output: [[1.2.4]]
Copy the code

Example 2:

Enter k =3, n = 9Output: [[1.2.6], [1.3.5], [2.3.4]]
Copy the code

Their thinking

With the combination of 1

The problem solving code

var combinationSum3 = function (k, n) {
    let ans = [];
    let backTracing = (start, path) = > {
        if (path.length === k && path.reduce((acc, prev) = > acc += prev) === n) {
            ans.push(path.slice())
            return
        }
        for (let i = start; i <= 9; i++) {
            path.push(i)
            backTracing(i + 1, path)
            path.pop(i)
        }
    }
    backTracing(1[]),return ans
};
Copy the code

2.8-17. Alphabetic combinations of telephone numbers

Given a string containing only the numbers 2-9, return all the letter combinations it can represent. The answers can be returned in any order.

The mapping of numbers to letters is given as follows (same as a telephone key). Note that 1 does not correspond to any letter.

Example 1:

Enter: digits ="23"Output:"ad"."ae"."af"."bd"."be"."bf"."cd"."ce"."cf"]
Copy the code

Example 2:

Enter: digits =""Output: []Copy the code

Example 3:

Enter: digits ="2"Output:"a"."b"."c"]
Copy the code

Tip: 0 <= digits. Length <= 4 digits[I] is a number in the range [‘2’, ‘9’].

Their thinking

1. Finds the alphabetic string for the current button
2. Concatenate the string combination corresponding to the button
3. If the option satisfies the length, add the result

The problem solving code

var letterCombinations = function (digits) {
    if(! digits.length)return []
    const dic = {
        2: 'abc'.3: 'def'.4: 'ghi'.5: 'jkl'.6: 'mno'.7: 'pqrs'.8: 'tuv'.9: 'wxyz',
    }, ans = [];

    let backTracing = (cur, index) = > {
        if (index > digits.length - 1) { // If the option meets the length, add the result
            ans.push(cur)
            return
        }
        let curDic = dic[digits[index]] // Find the letter string corresponding to the current button
        for (let prop of curDic) {
            backTracing(cur + prop,index+1) // Concatenate the string combination corresponding to the button
        }
    }
    backTracing(' '.0)
    return ans
};
Copy the code

2.9-08.01. Three-step problem

Three-step problem. A child is walking up a staircase. The staircase has n steps, and the child can walk up one, two or three at a time. Implement a method that counts the number of ways a child can walk up stairs. The result may be large and you need to set the result module to 1000000007.

Example 1:

Enter n =3Output:4Explanation: There are four ways to goCopy the code

Example 2:

Enter n =5Output:13
Copy the code

Note: n ranges from [1, 1000000]

Solution code (will time out)

 var waysToStep = function (n) {
    let ans = [], map = [1.2.3]
    let backTracing = (path, sum) = > {
        if (sum >= n) {
            if (sum == n) {
                ans++;
            }
            return
        }
        for (let i = 0; i < 3; i++) {
            path.push(map[i]);
            backTracing(path, sum + map[i])
            path.pop(i)
        }
    }
    backTracing([], 0)
    return ans
};
Copy the code

Dynamic programming solution

/ * * *@param {number} n
 * @return {number}* /
var waysToStep = function (n) {
    let dp =[],mod = 1000000007;
    dp[0] =0,dp[1] =1,dp[2] =2,dp[3] =4;
    for (let i = 4; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod
    }
    return dp[n]
};
Copy the code

2-10-40. Sum of combinations II

Given an array of candidates and a target number target, find all combinations of the candidates that can be the sum of the number and target.

Each number in the candidates must be used only once in each combination. Note: The solution set cannot contain repeated combinations.

Example 1:

Enter: candidates = [10.1.2.7.6.1.5], target = 8, output: [[1.1.6],
[1.2.5],
[1.7],
[2.6]]Copy the code

Example 2:

Enter: candidates = [2.5.2.1.2], target = 5, output: [[1.2.2],
[5]]Copy the code

1 <= candidate. length <= 100 1 <= candidate. length <= 50 1 <= target <= 30

Their thinking

The same idea as combination 1

The problem solving code

/ * * *@param {number[]} candidates
 * @param {number} target
 * @return {number[][]}* /
 var combinationSum2 = function (candidates, target) {
    candidates.sort((a,b) = >a-b)
    let ans = [];
    let backTracing = (start, path, sum) = > {
        if (sum >= target) {
            if (sum === target) {
                ans.push(path.slice())
            }
            return
        }
        for (let i = start; i < candidates.length; i++) {
            if (i - 1 >= start && candidates[i - 1] == candidates[i]) {
                continue;
            }
            path.push(candidates[i])
            backTracing(i + 1, path, sum + candidates[i])
            path.pop()
        }
    }
    backTracing(0[],0)
    return ans
};
Copy the code

2-11-47. Full array II

Given a sequence nums that can contain repeating digits, return all non-repeating full permutations in any order.

Example 1:

Enter: nums = [1.1.2] Output: [[1.1.2],
 [1.2.1],
 [2.1.1]]
Copy the code

Example 2:

Enter: nums = [1.2.3] Output: [[1.2.3], [1.3.2], [2.1.3], [2.3.1], [3.1.2], [3.2.1]]
Copy the code

1 <= nums.length <= 8-10 <= nums[I] <= 10

Their thinking

Same as above

The problem solving code

var permuteUnique = function (nums) {
   let ans = [];
   let used = Array(nums.length).fill(false)
   let backTracing = (start, path) = > {
       if (start === nums.length) {
           ans.push(path.slice())
           return
       }
       for (let i = 0; i < nums.length; ++i) {
           if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {continue;
           }
           path.push(nums[i])
           used[i] = true
           backTracing(start + 1, path)
           used[i] = false
           path.pop()
       }
   }
   nums.sort((a, b) = > a - b)
   backTracing(0[]),return ans

};
Copy the code

Third, summary

The backtracking algorithm is mainly used. To solve a backtracking problem is actually a decision tree traversal process.

3.1 template

let backtracking=(Path, select list) = >{
    if(End condition satisfied) {store path;return;
    }
    for(Select: path, select list) {make a selection; Backtracking (path, select list);/ / recursionBacktrace, undo processing result}}Copy the code

That is:

1. 1. Path: The choices already made.
2. 2. Selection list: The choices you can currently make.
3. 3. End condition: that is, the condition when you reach the bottom of the decision tree and can no longer make a choice.

3.2 Pruning function

1. 1. Use constraints to cut off the subtree of viable solutions that cannot be obtained
2. 2. Use the objective function to cut the subtree of the optimal solution that cannot be obtained

3.3 General steps of retrospective method:

1. 1. Set the initialization scheme (assign initial values to variables, read known data, etc.)
2. 2. Change the way to test. If all the tests are finished, turn to the side (7)
3. 3. Judge whether this method is successful (by constraint function), if not, go to (2)
4. 4. Try again before you succeed
5. 5. If the correct scheme is not found, go to (2)
6. 6. To find a solution to record and print
7. 7. Step back (backtrack), if not back to the end, turn (2)
8. 8. If it has retreated to the end, it will end or print no solution

Keep going!!

Iv. References

1. LeetCode notes — Understanding recursion and backtracking

2. Graphical backtracking algorithm graphical backtracking algorithm

3. Summary of the backtracking algorithm Summary of the backtracking algorithm