如大家所熟悉的回溯算法是非常常见的一类经典问题类型它可以看成每次扩展一个情况扩展解空间直到达到边界条件或者找到条件的所有解。在这篇文章中我们主要讨论回溯问题常见的两种写法和它们适用的题目。解法一先添加再回溯在递归调用之前将当前的子集添加到结果列表中然后进行递归调用再在递归调用之后将最后添加的元素从子集中移除以回溯到上一层。Cclass Solution { public: void backtrack(vectorvectorint res, vectorint tmp, vectorint 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(); //撤销选择 } } vectorvectorint subsets(vectorint nums) { vectorvectorint res; vectorint tmp; backtrack(res, tmp, nums, 0); return res; } };解法二先回溯后添加在递归调用之前不将当前的子集添加到结果列表中而是直接进行递归调用。在递归调用完成后再将当前元素添加到子集中再进行回溯到上一层。Cclass Solution { public: void backtrack(vectorvectorint res, vectorint tmp, vectorint 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(); //撤销选择 } vectorvectorint subsets(vectorint nums) { vectorvectorint res; vectorint tmp; backtrack(res, tmp, nums, 0); return res; } };这两种解法实质上是相同的只是在选择添加子集和进行回溯的时机上有所差异。第一种解法在每次遍历时都会将当前的子集加入到结果集中而第二种解法则是在递归结束时才将当前的子集加入到结果集中。结合下面的图能够清晰地理解这两种解法的差异其中加深的集合表示真正加入最终结果的数组的集合。两个解法的 index 的含义基本一致但是作用不同。它们都表示后续待选择数组的左边界而解法二会使用 index 作为判断加入结果集的边界条件。