Likou-Backtracking

2024-07-12

What is backtracking?

When searching for a certain node, if we find that the current node (and its child nodes) are not the required target, we roll back to the original node to continue searching and restore the status modified at the current node.

Remember two little tips,One is to pass the state by reference (&), and the other is to revert all state changes after the recursion is completed.

There are generally two situations for backtracking modification: one is to modify the last output, such as permutations and combinations; the other is to modify the access flag.

Remember, for example, searching for a string in a matrix.

46. Full Arrangement

topic
Given an array without repeated numbersnums, return itsAll possible permutations.you canIn any orderReturn the answer.

Example 1:
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
输入：nums = [0,1]
输出：[[0,1],[1,0]]
Example 3:
输入：nums = [1]
输出：[[1]]
hint:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
numsAll integers inDifferent

answer

To output all sorted combinations of the array, we can use backtracking.

First determine a position, then swap it with each subsequent position. After the swap, go to the next position. Then after this series of steps, you need to swap back the swapped positions. This is the backtracking method.


class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        back(nums,0,ans);
        return ans;
    }
    void back(vector<int>& nums,int n,vector<vector<int>>& ans){
        int i;
        if(n==nums.size()-1)
            ans.push_back(nums);
        for(i=n;i<nums.size();i++){
            swap(nums[i],nums[n]);
            back(nums,n+1,ans);
            swap(nums[i],nums[n]);
        }
    }
};

77. Combination

topic

Given two integersnandk, return range[1, n]All possiblekA combination of numbers.

You can pressAny orderReturn the answer.

Example 1:
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
Example 2:
输入：n = 1, k = 1
输出：[[1]]
hint:

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

题解

Set a count, calculate the number of each, and when count==k, put it into the array. This is different from the previous one, which was to perform permutations and combinations. This is a bit like selecting permutations.

Starting from 1-n, set up an extra array to store the results of each time. Count changes dynamically, assign i to count plus one, and select a number from (i+1, n) in dfs. Backtrack and count--.
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> c(k,0);
        int count;
        dfs(n,k,1,ans,c,count);
        return ans;
    }
    void dfs(int n,int k,int level,vector<vector<int>>& ans,vector<int>& c,int& count){
        int i;
 
        if(count==k){
            ans.push_back(c);
            return ;
        }
            
        for(i=level;i<=n;i++){
            c[count++]=i;
            dfs(n,k,i+1,ans,c,count);
            --count;
        }
    }
};

79.Unit Search

79. Word Search

topic

Given am x n2D Character Gridboardand a string wordword.ifwordexists in the grid, returnstrue; Otherwise, returnfalse 。

Words must be constructed in alphabetical order using letters in adjacent cells, where "adjacent" cells are those that are adjacent horizontally or vertically. Letters in the same cell may not be repeated.

Example 1:
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
Example 2:
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
Example 3:
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
hint:

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
boardandwordOnly uppercase and lowercase English letters

answer

Similar routine.

The dfs+backtracking method first defines a visit to mark whether the location has been marked each time the search is performed, to prevent the same location from being visited multiple times.

For a position, we need to perform boundary judgment to see if it has crossed the boundary. Then we need to judge whether it has been visited before, whether it has been successfully found, and whether the letter at this position is different from the target letter.

dfs, search around.


class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.empty())
            return false;
        int m=board.size(),n=board[0].size();
        vector<vector<bool>> visit(m,vector<bool>(n,false));
        int i,j;
        bool find=false;
        for(i=0;i<m;i++){
            for(j=0;j<n;j++)
                back(i,j,board,word,find,visit,0);
        }
        return find;
    }
    void back(int i,int j,vector<vector<char>>& board,string& word,
    bool& find,vector<vector<bool>>& visit,int level){
        if(i<0||i>=board.size()||j<0||j>=board[0].size())
            return ;
      
        if(visit[i][j]||find||board[i][j]!=word[level])
            return ;
        if(level==word.size()-1){
            find=true;
            return ;
        }
        visit[i][j]=true;
        back(i+1,j,board,word,find,visit,level+1);
        back(i-1,j,board,word,find,visit,level+1);
        back(i,j+1,board,word,find,visit,level+1);
        back(i,j-1,board,word,find,visit,level+1);
        visit[i][j]=false;
    }
};

51. Queen N

51. N Queen

topic

According to the rules of chess, the queen can attack the pieces in the same row, column or diagonal line as the queen.

n Queen's ProblemThe study is about hownThe queen is placedn×non the chessboard and prevent the queens from attacking each other.

Give you an integern, returns all distinctn Queen's Problems solution.

Each solution contains a differentn Queen's ProblemA chess piece placement scheme in which'Q'and'.'They represent the queen and the vacant seat respectively.

Example 1:
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
Example 2:
输入：n = 1
输出：[["Q"]]
hint:

1 <= n <= 9

题意

N queens requires three marking functions, one for the columns, one for the main diagonal, and one for the subdiagonal.

Because there will be a queen in each row, we traverse the rows one by one, and when we successfully traverse to the last row and successfully place the queen, we are done. Therefore, there is no need to set a marking function for the row.

At this time, we can start from the first row and traverse by column. Determine whether the column is false, whether the main diagonal is false, and whether the secondary diagonal is false. If so, go to the next column. If not, set the position to Q, and then do the same search for the next row. Backtracking method, remember to restore the position and mark function after searching.

This diagonal and the secondary diagonal can be drawn on the coordinates, one is y=x+b, and the other is y=-x+b.

So b=yx, in order to make b>0, we add n. The other one is y+x.
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        if(n==0)
            return {};
        vector<string> board(n,string(n,'.'));
        vector<bool> c(n,false),l(2*n-1,false),r(2*n-1,false);
        back(n,ans,board,c,l,r,0);
        return ans;
    }
    void back(int n,vector<vector<string>>& ans,vector<string>& board,vector<bool>& c,
    vector<bool>& l,vector<bool>& r,int row){
        if(row==n){
            ans.push_back(board);
            return ;
        }
        int i;
        for(i=0;i<n;i++){
            if(c[i]||l[row-i+n]||r[row+i]){
                continue;
            }
            board[row][i]='Q';
            c[i]=l[row-i+n]=r[row+i]=true;
            back(n,ans,board,c,l,r,row+1);
            board[row][i]='.';
            c[i]=l[row-i+n]=r[row+i]=false;
        }
    }
};

Summarize

For the backtracking method, first find the boundary conditions and the end conditions. Generally, i is set equal to the number of rows.

The boundary condition is generally not to cross the boundary.

Usually you also need to set a marking function. Then visit one line at a time or one position at a time, and set the visited marking function to true. Then continue to the next one or the next line (usually recursively). Then restore the above marking function and board (usually set one as the answer) after the end. If it meets the requirements, push_back to the ans array.

Technology Sharing