回溯求解框架
在回溯算法套路详解中，作者给出了一个回溯算法的框架：
result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 判断是否需要剪枝 做选择 backtrack(路径, 选择列表) 撤销选择
上面这个真的就是个框架，有几个需要注意的点：1. 回溯函数的参数是什么，怎么定？2. 结束条件需要依据题意来确定；3. 在进入for循环遍历选择之后还需要判断是否需要剪枝。4. 在选择列表中做出选择。5. 进入递归，进入下一层递归树。6.撤销选择，去穷举另外一个选择。
基于回溯框架求解之全排列
说这么多也没什么用，结合一个例子来说明：比如Leetcode第46题全排列：给定一个 没有重复 数字的序列，返回其所有可能的全排列。示例：
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
我习惯先考虑主逻辑，也就是for循环内部如何工作，然后去补充上面提到的5个注意点，那么主逻辑就是我们每次都可以从[1,2,3]中做出选择，选择这个节点是否需要加入到我们的临时结果中。因为做完这个选择之后，我们还要遍历其它的选择，因此最后还需要撤销这个选择。这个撤销的理解就是，比如第一次循环我们选择了数字1，那么下一次就是选择2了，而1这个选择我们就需要撤销，此时的for循环就可以写成：
void backtrack(vector<int>& nums, vector<int>& path){ for(int i=0; i<nums.size(); ++i){ path.push_back(nums[i]); backtrack(nums, path); path.pop_back(); } }
初步的想法就形成了，不断地对数组中的数字进行组合，可以看作树的一个全展开递归调用。上述代码还是有一些小问题的，最明显的就是这个会无限递归下去，因此我们首先可以加上结束条件：
void backtrack(vector<int>& nums, vector<int>& path){ if(path.size() == nums.size()){ res.push_back(path); return; } for(int i=0; i<nums.size(); ++i){ path.push_back(nums[i]); backtrack(nums, path); path.pop_back(); } }
因为这里每次循环都是从0开始，也就是每次都会遍历整个数组，比如会出现添加了[1, 1, 1]的这种情况，注意到题目给定的条件，是一个没有重复数字的序列。因此当一个元素被选定添加到path数组中之后，我们就不能在下一层中再次选择它，为了实现上述的这个功能，我们可以设置一个集合s，用来记录已经被选择过的元素，如果新加入的元素在集合中的话，我们就不用再往下走了，相当于一个剪枝的过程：
void backtrack(vector<int>& nums, vector<int>& path, unordered_set<int>& s){ if(path.size() == nums.size()){ res.push_back(path); return; } for(int i=0; i<nums.size(); ++i){ if(s.count(nums[i])) continue; s.insert(nums[i]); path.push_back(nums[i]); backtrack(nums, path, s); s.erase(nums[i]); path.pop_back(); } }
到此回溯的整个代码就写完了，整体代码如下：
class Solution { public: vector<vector<int>> res; vector<vector<int>> permute(vector<int>& nums) { vector<int> path; unordered_set<int> s; backtrack(nums, path, s); return res; } void backtrack(vector<int>& nums, vector<int>& path, unordered_set<int>& s){ if(path.size() == nums.size()){ res.push_back(path); return; } for(int i=0; i<nums.size(); ++i){ if(s.count(nums[i])) continue; s.insert(nums[i]); path.push_back(nums[i]); backtrack(nums, path, s); s.erase(nums[i]); path.pop_back(); } } };
这里我们是用了一个集合来记录被访问过的元素，之后好用于剪枝，我们也可以用别的方式来记录已经被访问过的元素，比如像数组，这里可能就会有小伙伴问了，用集合就可以了，为什么还要用数组呢？其实用数组的解法更加通用一点，因为如果遇到了数组中有重复元素的话，那我们用集合的话就不方便去记录哪个元素被访问过了什么的。因此我们把集合换成数组就可以得到另一种解法：
class Solution { public: vector<vector<int>> res; vector<vector<int>> permute(vector<int>& nums) { vector<int> path; vector<int> vis(nums.size(), 0); backtrack(nums, path, vis); return res; } void backtrack(vector<int>& nums, vector<int>& path, vector<int>& vis){ if(path.size() == nums.size()){ res.push_back(path); return; } for(int i=0; i<nums.size(); ++i){ if(vis[i]) continue; vis[i] = 1; path.push_back(nums[i]); backtrack(nums, path, vis); vis[i] = 0; path.pop_back(); } } };
基于回溯框架求解之全排列 II
既然说到了数组中有重复元素的情况，那就来看一下这个全排列的进阶：Leetcode47全排列 II：给定一个可包含重复数字的序列nums，按任意顺序 返回所有不重复的全排列。举例如下：
输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]
依据之前的所述，我们可以很容易写出整颗递归树的全展开形式：
void backtrack(vector<int>& nums, vector<int>& path){ if(path.size() == nums.size()){ res.push_back(path); return; } for(int i=0; i<nums.size(); ++i){ path.push_back(nums[i]); backtrack(nums, path); path.pop_back(); } }
问题的关键就在于剪枝的过程。首先第一点被访问过的元素应该被剪枝，这个可以采用一个数组来记录哪些元素已经被访问过了，访问过了的元素就剪枝即可，这一点与第一道全排列一样。不同点在于现在数组中有重复元素，比如像两个相邻的[1, 1]先访问哪一个后访问哪一个是没有关系的。我们只需要去保证这种情况只会被访问一次即可，其它的情况就剪枝，我们先按照顺序情况求解即可，这里的顺序情况说的是，比如说重复的元素按照从左往右顺序取一遍即可。
那么它满足的条件就是当前元素要等于上一个元素，并且上一个元素被访问过了，没被访问过的话就说明不是顺序取值的情况，需要跳过。而这种情况的满足需要一个前提，就是相同的元素需要排列在一起，我们可以得到如下代码：
class Solution { public: vector<vector<int>> res; vector<vector<int>> permuteUnique(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<int> vis(nums.size(), 0); vector<int> path; backtrack(nums, path, vis); return res; } void backtrack(vector<int>& nums, vector<int>& path, vector<int>& vis){ if(path.size() == nums.size()){ res.push_back(path); return; } for(int i=0; i<nums.size(); ++i){ if(vis[i] || i>0 && nums[i]==nums[i-1] && !vis[i-1]){ continue; } vis[i] = 1; path.push_back(nums[i]); backtrack(nums, path, vis); path.pop_back(); vis[i] = 0; } } };
上述代码中的最难理解的部分可能就是剪枝部分的代码了：
if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) { continue; }
这里较难理解的就是这段代码，其实就是一个剪枝的过程。我们举个例子，来说明!vis[i - 1]这一项：假设我们有两个1的数组，为了加以区分我们把它设置成[1_1, 1_2]，把这两个元素的递归树全展开我们可以得到2 × 2 = 4 2 \times 2=42×2=4种情况：
[1_1, 1_1] [1_1, 1_2] [1_2, 1_1] [1_2, 1_2]
- 上述四种情况的第一种
[1_1, 1_1]中的第二个1_1来自第二轮循环中i等于0的情况，而第二次访问i=0的时候，vis[i]已经被置1了，所以continue跳过，回溯到上一个节点。 - 上述四种情况的第二种
[1_1, 1_2]中的1_2来自第二轮循环中i等于1的情况，此时(i > 0 && nums[i] == nums[i - 1])满足条件，但是vis[i-1]表示第一个1_1是否被访问过，它被访问过，所以vis[i-1]=1，因此!vis[i-1]=0，条件不满足，[1_1, 1_2]这一条会被选中。 - 上述四种情况的第三种
[1_2, 1_1]来自第一轮循环选中1_2的情况，注意此时已经回溯回去了，此时的1_1的访问标记位vis[0]=0，未被访问过，并且i=1。所以我们需要看后面的条件(i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])，此时i > 0 && nums[i] == nums[i - 1]条件都满足，vis[i-1]=vis[1-1]=vis[0]=0，!vis[i-1]=1条件满足，选择continue跳过，回溯到上一个节点。 - 上述四种情况的第四种[1_2, 1_2]，中的第二个
1_2来自第二轮循环中i等于1的情况，而第二次访问i=0的时候，vis[i]=vis[1]=1已经被置1了，所以continue跳过，回溯到上一个节点。
if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) { continue; }
而把上述代码中的!vis[i-1]改为vis[i-1]的话也是可以的，此时就相当于把第2和第3中的结果互换一下。就相当于两个重复元素，一个从前往后添加进数组中一个从后往前添加进数组中。从前往后的话就是[1_1, 1_2]这种情况，从后往前的话就是[1_2, 1_1]这种情况。
