回溯的思維方式

回溯算法

• 全排列 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;
    }
           

心得總結

• 學算法得從架構入手，架構了解思路，剩下的就是一些特殊處理

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