干货分享：图解两种常见回溯解法（一）

如大家所熟悉的，回溯算法是非常常见的一类经典问题类型，它可以看成每次扩展一个情况（扩展解空间），直到达到边界条件或者找到条件的所有解。

在这篇文章中，我们主要讨论回溯问题常见的两种写法和它们适用的题目。

解法一：先添加再回溯

在递归调用之前将当前的子集添加到结果列表中，然后进行递归调用，再在递归调用之后将最后添加的元素从子集中移除，以回溯到上一层。

C++

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; } };

解法二：先回溯后添加

在递归调用之前不将当前的子集添加到结果列表中，而是直接进行递归调用。在递归调用完成后，再将当前元素添加到子集中，再进行回溯到上一层。

C++

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 作为判断加入结果集的边界条件。