Day12(回溯法)——LeetCode51.N皇后39.组合总和

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 感想

  想理解回溯，感觉重要的是理解递归，递归猛一看感觉还不错，但是当其在语句中运行时，往往分不清什么时候运行哪一句，什么时候运行下一句，返回时哪些变量恢复到递归前的值，哪些变量需要自己手动回溯等等。
  还需要自己手动画一下递归树，以及剪枝的过程，回溯的过程。此外在设计函数时也需要仔细思考，好的函数往往能事半功倍。总之自己对回溯对递归理解的还远远不够。。。真的头大。。。