I took a new project and was busy for some time. This article has been delayed for a long time... I quit at the end of the month!
Today, I reviewed the backtracking algorithm. It is obviously a very basic thing. When I write it, I feel very difficult and unclear. Look at the code of the full permutation problem written before, and you'll have your idea. Sure enough, the algorithm routine template is still very important. The template is not afraid of any variants in hand, and must be reviewed in time to strengthen memory. So I decided to summarize the routine of classical algorithms, starting with backtracking.

preface

Backtracking algorithm is to perform a depth first traversal of the tree or graphic structure. In fact, it is similar to the search attempt process of enumeration to find the solution of the problem in the traversal process. Depth first traversal has a characteristic: when it is found that the solution conditions are not met, it will return and try another path, which is usually called "pruning". At this time, the object type variable needs to be reset as before, which is called "state reset".

1, Eight queens problem

The eight queens problem can be said to be a classic example of backtracking algorithm. I remember a big assignment in the algorithm class of my sophomore year. I gave myself one of more than a dozen questions to do. I chose the eight queens problem at that time. At first, I couldn't write it. Later, I referred to the online code (this is the advantage of the classic title. I can't copy it. Hahaha). After understanding the online code, I changed it into two versions. One version can draw the eight queens of the chessboard, and the other version only counts the number of N queens. I handed it in together.

Eight queens: place Eight queens in Eight queens × 8 on the chessboard, and make the Queens unable to attack each other. (in chess, the Queen's attack condition is on the same row, column or slash)

If you use the exhaustive method, you need to try 8 ^ 8 cases. At this time, the characteristic of backtracking "pruning" reflects the advantage. For example, if we first put the Queen in the first row on the first column, then the Queen in the second row obviously cannot be placed on the first column or the second column, so we put it on the third column, and then the Queen in the third row obviously cannot be placed on columns 1, 2, 3 and 4, and so on. When it does not meet the requirements, we resolutely go back to the previous step and find a new path, which is the core idea of backtracking.

A code to find the solution quantity:

class Solution {
public:
	int result=0;
    int totalNQueens(int n) {
    	//Initialize an empty chessboard
    	vector<int> board(n,-1);
    	backtrack(0,board);
    	return result;
    }
    void backtrack(int row,vector<int>& board){
    	//End condition
    	if(row==board.size()) 
    	{
    		result++;
    		return;
    	}

    	for(int col=0;col<board.size();col++)
    	{
    		if(!isValid(board,row,col)) continue;
    		//Make a choice
    		board[row]=col;
    		//next row
    		backtrack(row+1,board);
    		//Reset
    		board[row]=-1;
    	}
    }
    bool isValid(vector<int> board,int row,int col){
    	//Judge whether the current position conflicts with the previous lines
    	for(int r=0;r<row;r++)
    	{
    		int c=board[r];
    		if(c==col||abs(r-row)==abs(c-col)) return false;
    	}
    	return true;
    }
};

2, Total permutation problem

Full permutation problem: given an array without duplicate numbers, return all possible full permutations.
The full permutation problem can be said to be the standard template of backtracking algorithm. A very clear implementation idea is to select the next state - recursion - state reset.
The full permutation code is as follows:

class Solution {
public:
	vector<vector<int>> result;
    vector<vector<int>> permute(vector<int>& nums) {
    	vector<int> line;
    	backtrack(line,nums);
    	return result;
    }
    void backtrack(vector<int>& line,vector<int> nums){
    	if(line.size()==nums.size())
    	{
    		result.push_back(line);
    		return;
    	}
    	for(int i=0;i<nums.size();i++)
    	{
    		bool flag=true;
    		for(int j=0;j<line.size();j++)
    			if(line[j]==nums[i]){
    				flag=false;
    				break;
    			}
    		if(!flag) continue;
    		line.push_back(nums[i]);
    		backtrack(line,nums);
    		line.pop_back();
    	}
    }
};

3, Backtracking algorithm template

The code is as follows (example):

//Backtracking algorithm routine
class Solution {
public:
    //Define global variables, such as the number of results to return, or the result set
    //Define visited []
    vector<vector<int>> result;
    vector<vector<int>> permute(vector<int>& nums) {
        //Initialize global variables
        //Define track (indicating current status)
        vector<int> line;
        //Execute the backtracking algorithm, using the initial parameters
        backtrack(line,nums);
        //Return results
        return result;
    }
    void backtrack(vector<int>& line,vector<int> nums){
        //Define the end state and where to stop
        if(line.size()==nums.size())
        {
            result.push_back(line);
            return;
        }
        //Traverse all possible next states
        for(int i=0;i<nums.size();i++)
        {
            //Exclude the next state that does not meet the conditions (pruning)
            bool flag=true;
            for(int j=0;j<line.size();j++)
                if(line[j]==nums[i]){
                    flag=false;
                    break;
                }
            if(!flag) continue;
            //Modify the track to the new status, and modify visited []
            line.push_back(nums[i]);
            //Perform backtracking on the new status and pay attention to modifying the parameters
            backtrack(line,nums);
            //Return to original status
            line.pop_back();
        }
    }
};

summary

In short, the backtracking algorithm is an exhaustive list with pruning. It must be very time-consuming to list all possibilities. Writing the pruning conditions can greatly reduce the time complexity.
With the template, it's much easier to do the topic, and the idea is clear. Just put it in.