1 前言

??今天刷了三道回溯法和一道每日推薦，三道回溯法也迷迷糊糊的，每日推薦把自己繞進去了，雖然是一道之前做過的題的變種。刷的腦子疼。。。今天挑兩道回溯題寫一下吧，其中有一道是之前做過的N皇后，今天在詳細寫一寫。

2 LeetCode51.N皇后(LeetCode)

2.1 題目描述

??題目描述如下：

??示例如下：

2.2 題目分析及解決

??思路大概就是從第一行的第一列開始放置皇后，然后遞歸下一行，直到找到第一個皇后在第一行第一列的所有解，然后回溯到第一行，進行第二列的搜索。
??這里用vector<string> path記錄每個解，定義queue(int row,int n)來找第row行合法的皇后位置，n是總行數。當我們找到第n行時，且能找到解，則將該結果保存到答案中，然后返回，尋求其他解。
??嘗試把皇后放在該行的每一列中，若與之前的皇后放置位置沒有沖突，則放置皇后。這里就發現，我們需要一個數組來保存之前皇后放置的位置。設state[i]=j，表示第i行皇后放在第j列，因此每次放置皇后，都只需要檢驗其與之前的行的皇后有無矛盾即可，將在同一列，對角線以及反對角線的情況寫出來，觀察下標可以很容易進行判斷：

bool conflict(int r,int j){for(int i=0;i<r;i++){if(state[i]==j||(abs(state[i]-j)==abs(r-i))){return true;}}return false;}

??當遞歸找下一行后，需要在其遞歸返回后恢復現場，即將state和path恢復原始狀態。
??完整代碼如下：

#include<string>
#include<vector>
class Solution {
public:vector<vector<string>> ans;vector<string> path;vector<int> state;bool conflict(int r,int j){for(int i=0;i<r;i++){if(state[i]==j||(abs(state[i]-j)==abs(r-i))){return true;}}return false;}void queue(int row,int n){if(row==n){ans.push_back(path);return;}for(int j=0;j<n;j++){if(!conflict(row,j)){//記錄當前行皇后的位置state[row]=j;//放置皇后path[row][j]='Q';queue(row+1,n);//回溯path[row][j]='.';state[row]=-1;}}}vector<vector<string>> solveNQueens(int n) {path=vector<string>(n,string(n,'.'));state=vector<int>(n,-1);queue(0,n);return ans;}
};

3 LeetCode39.組合總和(LeetCode39)

3.1 題目描述

??題目描述如下：

??具體實例如下：

3.2 題目分析及解決

??感覺好像是重復背包問題(有點記不清了)。思路大概都好想，假設現在判斷是否使用第i個數，若使用nums[i]后，其仍沒超過target，則可以繼續從第i個數進行遞歸(即再次判斷能否使用nums[i])；若超過了target，則需要嘗試使用別的數，若其余數都不符合，則回溯到第i個數前，嘗試使用別的數。這里注意到，如果我們提前將數組進行排序，則當使用nums[i]后超過target后，則nums[i]后面的數也一定不能使用，從而提前結束遞歸(剪枝)。
??具體代碼如下：

class Solution {
public:vector<vector<int>> ans;vector<int> path;void dfs(vector<int>& candidates,int target,int i){//找到正確解，放入結果if(target==0){ans.push_back(path);return;}//若當前和大于target，返回，遞歸會嘗試放下一個元素if(target<0) return;for(int start=i;start<candidates.size();start++){//不斷放入第i個元素if(target-candidates[start]>=0){path.push_back(candidates[start]);//遞歸處理，可重復使用元素，因此下一次開始仍然是startdfs(candidates,target-candidates[start],start);//回溯，移除當前解，嘗試其他可能//target隱式的回溯，因為其是函數變量path.pop_back();}}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());dfs(candidates,target,0);return ans;}
};

4 感想

??想理解回溯，感覺重要的是理解遞歸，遞歸猛一看感覺還不錯，但是當其在語句中運行時，往往分不清什么時候運行哪一句，什么時候運行下一句，返回時哪些變量恢復到遞歸前的值，哪些變量需要自己手動回溯等等。
??還需要自己手動畫一下遞歸樹，以及剪枝的過程，回溯的過程。此外在設計函數時也需要仔細思考，好的函數往往能事半功倍。總之自己對回溯對遞歸理解的還遠遠不夠。。。真的頭大。。。