回溯算法是非常常见的一类经典问题类型，它可以看成每次扩展一个情况（扩展解空间），直到达到边界条件或者找到条件的所有解。在这篇文章中，我们主要讨论回溯问题常见的两种写法和它们适用的题目。
基础写法
以力扣的78.子集为例，这一题就是找到给定数组的所有子集，数组中的元素互不相同，这是一题典型的回溯题，通常会有两种模板写法。
解法一（先添加再回溯）：在递归调用之前将当前的子集添加到结果列表中，然后进行递归调用，再在递归调用之后将最后添加的元素从子集中移除，以回溯到上一层。
class Solution
{
public:
void backtrack(vector<vector<int>> &res, vector<int> tmp,
vector<int> nums, int index)
{
res.emplace_back(tmp); //加入结果集
for (int i = index; i < nums.size(); i++)
{ //遍历每个元素
tmp.push_back(nums[i]); // 加入第i个元素
backtrack(res, tmp, nums, i + 1); //递归
tmp.pop_back(); //撤销选择
}
}
vector<vector<int>> subsets(vector<int> &nums)
{
vector<vector<int>> res;
vector<int> tmp;
backtrack(res, tmp, nums, 0);
return res;
}
};
解法二（先回溯后添加）：在递归调用之前不将当前的子集添加到结果列表中，而是直接进行递归调用。在递归调用完成后，再将当前元素添加到子集中，再进行回溯到上一层。
class Solution
{
public:
void backtrack(vector<vector<int>> &res, vector<int> tmp,
vector<int> nums, int index)
{
if(index == nums.size())
{//加入结果集
res.emplace_back(tmp);
return;
}
backtrack(res, tmp, nums, index+ 1); //不加元素并递归
tmp.push_back(nums[index]); //加入第index个元素
backtrack(res, tmp, nums, index+ 1); //递归
tmp.pop_back(); //撤销选择
}
vector<vector<int>> subsets(vector<int> &nums)
{
vector<vector<int>> res;
vector<int> tmp;
backtrack(res, tmp, nums, 0);
return res;
}
};
这两种解法实质上是相同的，只是在选择添加子集和进行回溯的时机上有所差异。第一种解法在每次遍历时都会将当前的子集加入到结果集中，而第二种解法则是在递归结束时才将当前的子集加入到结果集中。
结合下面的图，能够清晰地理解这两种解法的差异，其中，加深的集合表示真正加入最终结果的数组的集合。
两个解法的index的含义基本一致，但是作用不同。它们都表示后续待选择数组的左边界，而解法二会使用index作为判断加入结果集的边界条件。
题目分类
在不同的题目中，可能适用不同的解法，也可能需要对解法进行相应的改变，以下总结了经典的回溯题目的要素。
| 题目 | 题意 | 限制条件 | 选择是否可重复 | 数组元素是否可能相同 |
|---|---|---|---|---|
| 78.子集 | 元素互不相同的数组的所有子集 | 考虑到数组的最后一个数 | ❌ | ❌ |
| 90.子集II | 元素可能相同的数组的所有不重复子集 | 考虑到数组的最后一个数 | ❌ | ✔️ |
| 77.组合 | 确定的数组（1-n)的所有k个数的集合 | 当前已选择元素的个数为k | ❌ | ❌ |
| 39.组合总和 | 元素互不相同的数组找出和为target的组合 | 考虑到数组的最后一个数或者当前已选择的元素和为target | ✔️ | ❌ |
| 40. 组合总和 II | 元素可能相同的数组，找出和为target的组合 | 考虑到数组的最后一个数或者当前已选择的元素和为target | ❌ | ✔️ |
| 216.组合总和III | 确定的数组（1-9）找出和为target的k个数的组合 | 当前已选择元素和为target，个数为k | ❌ | ❌ |
从表中归纳的情况来看，40.组合总和II和90.子集II两题因为都需要考虑可能重复生成子集，所以整体解法会比较相近（在下一节会具体展开）。39.组合总和的一个特殊情况就是可以重复选择元素，在两种解法中只需要修改调用函数时传入的index，并不是非常复杂的操作。 其余的题目都比较常规，只需要确定好加入集合的条件即可。
去重操作
在一些题目中会出现一个复杂的问题，即当一个集合有重复元素时，题目希望最终得到的结果集合不包含重复的元素。如果按照模板的做法，就算每个元素只选择一次，出现重复的选择仍然是不可避免的，针对这样的问题，上述的两种解法分别需要做不同的修改。
以40.组合总和II这一题为例，这题要求在一个元素可能相同的数组中找出和为target的无重复组合。以下是两种解法为了解决重复生成问题下做的改动。
解法一
解法一通过在for循环里加入判断条件，让每一层不出现重复的元素的选择从而避免了结果的重复。
// 解法一去重
class Solution
{
public:
void backtrack(vector<vector<int>> &ans, vector<int> &tmp, vector<int> &candidates, int target, int idx)
{
if (target == 0)
{ //加入结果集
ans.emplace_back(tmp);
return;
}
for (int i = idx; i < candidates.size() && target - candidates[i] >= 0; i++)
{
//如果当前的元素与前一个元素重复，那么就不需要再加入这个元素
if (i > idx && candidates[i] == candidates[i - 1])
continue;
tmp.emplace_back(candidates[i]);
backtrack(ans, tmp, candidates, target - candidates[i], i + 1);
tmp.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
{
vector<vector<int>> ans;
vector<int> tmp;
sort(candidates.begin(), candidates.end());
backtrack(ans, tmp, candidates, target, 0);
return ans;
}
};
以candidates = [1,2,2,3,5], target = 4为例，解法一的去重如下图所示。红色的就是去重剪枝掉的（实际上不存在，只是为了便于理解而展示），蓝色的是最后添加到结果集的满足条件的集合。
在下图中，可以看到每个集合的总和都不会超过target，这是因为在for循环时使用的限定条件target-candidate[i]>=0能够控制扩展的集合的总和不超过给定的数，这样就实现了剪枝的效果。
解法二
解法二核心要做的和解法一没有太多的区别，包括限定条件加入结果集、剪枝的操作、去重操作。
值得注意的是，基于解法二的去重操作在不加该元素递归的语句后加入重复的判定，同时还需要引入一个布尔变量。这个变量choose会记录前一个元素是否被选中，当前一个元素选中，并且和当前的元素相同时，就不需要再次扩展这种情况了。如果没有这个变量的话，就没办法确定是否选择过这个元素，有可能会造成情况的遗漏。
//解法二去重
class Solution {
public:
void backtrack(vector<vector<int>>& ans, vector<int>& tmp, vector<int>& candidates, int target, int idx, bool choose) {
if (target == 0)
{//加入结果集
ans.emplace_back(tmp);
return;
}
// 剪枝操作
if (idx == candidates.size() || target < 0)
return;
//不加元素并递归，choose传入false
backtrack(ans, tmp, candidates, target, idx + 1, false);
//如果当前未选择过前一个元素
// 并且当前元素与前一个元素重复了，这种情况就不需要再加入这个元素了
if (!choose && idx > 0 && candidates[idx] == candidates[idx - 1])
return;
tmp.emplace_back(candidates[idx]); // 选择当前元素
backtrack(ans, tmp, candidates, target - candidates[idx], idx + 1, true); // 回溯
tmp.pop_back(); //撤销选择
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> tmp;
sort(candidates.begin(), candidates.end());
backtrack(ans, tmp, candidates, target, 0, false);
return ans;
}
};
同样以candidates = [1,2,2,3,5], target = 4为例，解法二的去重如下图所示，红色和蓝色的示例同上。可以看到，当第一个2没有被选时，再次选的话就会被剪枝。
总体而言，这两种解法实际上都能够解答这类型的题，整体而言解法一要更加简洁好想，解法二有一些绕，需要完全想清楚整个递归的过程才不容易出错。
总结
以上我们讨论了回溯算法常用的两种解法以及其进阶的去重做法。总的来说，根据题目的不同要求和限制条件，适合的解法也有所不同。希望这篇文章的讲解能够让你加深对回溯算法的理解，并更灵活地运用基本的解法和技巧。