回溯的思维方式

回溯算法

• 全排列 Midium
• N皇后问题 Hard
• 心得总结

• 回溯思想就是

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
           

全排列 Midium

46. 全排列- 力扣（LeetCode） (leetcode-cn.com) Midium

vector<vector<int>> ans;
vector<int> path;

void backtrack(vector<int>& nums, vector<bool>& used) {
	if (path.size() == nums.size()) {
	//满足条件
		ans.push_back(path);
		return;
	}

	for (int i = 0; i < nums.size(); ++i) {
		//做选择
		if (used[i]) {
			continue;
		}
		used[i] = true;
		path.push_back(nums[i]);
		backtrack(nums, used);
		//撤销选择
		path.pop_back();
		used[i] = false;
	}
}

vector<vector<int>> permute(vector<int>& nums) {
	ans.clear();
	path.clear();
	vector<bool> used(nums.size(), false);
	backtrack(nums, used);
	return ans;
}
           

N皇后问题 Hard

• 说是Hard题，其实只是比全排列多写了一个判断函数，然而撤销处理更简单了

51. N 皇后- 力扣（LeetCode） (leetcode-cn.com) Hard

vector<vector<string>> ans;

    bool notValid(vector<string>& board,int row,int col){
        int n=board.size();
        //检查同一列是否有皇后
        for(int i=0;i<n;++i){
            if(board[i][col]=='Q'){
                return true;
            }
        }
		//检查右上角是否有皇后
        for(int i=row-1,j=col+1;i>=0&&j<n;--i,++j){
            if(board[i][j]=='Q'){
                return true;
            }
        }
		//检查左上角是否有皇后
        for(int i=row-1,j=col-1;i>=0&&j>=0;--i,--j){
            if(board[i][j]=='Q'){
                return true;
            }
        }

        return false;
    }

    void backtrack(vector<string>& board,int row){
        //满足条件
        if(row==board.size()){
            ans.push_back(board);
            return ;
        }

        int n=board[row].size();
        for(int col=0;col<n;++col){
        	//做选择
            if(notValid(board,row,col)){
                continue;
            }
            board[row][col]='Q';
            backtrack(board,row+1);
            //撤销选择
            board[row][col]='.';
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n,string(n,'.'));
        backtrack(board,0);
        return ans;
    }
           

心得总结

• 学算法得从框架入手，框架理解思路，剩下的就是一些特殊处理

  如果一个新的算法完全不懂，直接去跳入代码，必然事倍功半