解决一个回溯问题，本质是一个决策树的遍历

三要素：
1.路径：已经做出的选择
2.选择列表：当前可以做的选择
3.结束条件：到达决策树底层，不用再做选择

算法框架

result = []
def backTrack(path, choiceList):if 满足结束条件:result.push_back(path)returnfor choice in choiceList:做选择backTrack(path, choiceList)撤销选择

注意for循环中的递归
在递归前做选择
在递归后撤销选择

46. Permutations
    交换dfs

class Solution {
public:void backtrack(vector<int>& nums, vector<vector<int>>& res,int left, int right) {if(left == right) {res.push_back(nums);return;}for(int i = left; i < right; ++i) {// do choiceswap(nums[left], nums[i]);backtrack(nums, res, left + 1, right);// withdraw choiceswap(nums[left], nums[i]);}}vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;backtrack(nums, res, 0, nums.size());return res;}
};

傻瓜式完全照搬模板

class Solution {
public:void backtrack(vector<vector<int>>& res, vector<int>& nums, vector<int>& vis, vector<int>& path) {if(path.size() == nums.size()) {res.push_back(path);return;}for(int i = 0; i < nums.size(); ++i) {if(vis[i])continue;path.push_back(nums[i]);vis[i] = 1;backtrack(res, nums, vis, path);path.pop_back();vis[i] = 0;}}vector<vector<int>> permute(vector<int>& nums) {vector<int> vis(nums.size());vector<vector<int>> res;vector<int> path;backtrack(res, nums, vis, path);return res;}
};

这种时间反而是0
其中result和visit都可以是全局变量
通过传引用的方式实现
path的逻辑结构是栈

51. N-Queens
    笨比版面向过程编程

class Solution {
public:int length = 0;string nthQueen(int n) { // 得到一个字符串string s(length, '.');s[n] = 'Q';return s;}bool inbound(int i, int j) {if(i < length && i >= 0) {if(j < length && j >= 0) return true;}return false;}bool legal(vector<string>& path, int i, int j) {// 检测斜的就可for(int r = i - 1, c = j - 1; inbound(r, c); ) {if(path[r][c] == 'Q')return false;--r;--c;}for(int r = i - 1, c = j + 1; inbound(r, c); ) {if(path[r][c] == 'Q')return false;--r;++c;}return true;}void backtrack(vector<vector<string>>& res, vector<string>& path, vector<int>& vis) {if(path.size() == length) {res.push_back(path);return;}for(int i = 0; i < length; ++i) {if(vis[i])continue;//要放入".Q..."时 i为1 应为棋盘的第i列if(!legal(path, path.size(), i)) //col=i, row=path.size()continue;path.push_back(nthQueen(i));vis[i] = 1;backtrack(res, path, vis);path.pop_back();vis[i] = 0;}}vector<vector<string>> solveNQueens(int n) {length = n;vector<int> vis(n, 0); // 0 represents freshvector<vector<string>> res;vector<string> path;backtrack(res, path, vis);return res;}
};

终极简化版

class Solution {
public:vector<vector<string>> res;vector<string> ans;vector<bool> col, d, ud;int len;vector<vector<string>> solveNQueens(int n) {len = n;col = vector<bool> (n);d = vector<bool> (2 * n);ud = vector<bool> (2 * n);ans = vector<string> (n, string(n, '.'));dfs(0);return res;}void dfs(int u) // 即将要确定第u 行{if(u== len){res.push_back(ans);return;}for(int i=0;i< len;i++) // 第i列是否可以放入path{if(!col[i]&&!d[i+u]&&!ud[i-u+ len]){col[i] = d[i+u]=ud[i-u+ len]=true;ans[u][i]='Q';dfs(u+1);ans[u][i]='.';col[i] = d[i+u]=ud[i-u+ len]=false;}}}
};

每次加一行，不用考虑同行的情况
注意右对角线上i+j不变，左对角线上i-j+n不变
这两个vec初始要设置成长度2n

207. Course Schedule

class Solution {
public:bool dfs(vector<vector<int>>& adjacency, vector<int>& flag, int i) {if(1 == flag[i])return false;if(-1 == flag[i])return true;flag[i] = 1;for(int j: adjacency[i])if(!dfs(adjacency, flag, j))return false;flag[i] = -1;return true;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> adjacency(numCourses);vector<int> flag(numCourses, 0);for(int i = 0; i < prerequisites.size(); ++i) {adjacency[prerequisites[i][1]].push_back(prerequisites[i][0]);}for(int i = 0; i < numCourses; ++i)if(!dfs(adjacency, flag, i))return false;return true;}
};

通过dfs判断拓扑排序
要先声明adjacency长度为numcourse，不然无法访问adjacency[]