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

去重操作

在一些题目中会出现一个复杂的问题，即当一个集合有重复元素时，题目希望最终得到的结果集合不包含重复的元素。

如果按照模板的做法，就算每个元素只选择一次，出现重复的选择仍然是不可避免的，针对这样的问题，上述的两种解法分别需要做不同的修改。

解法一：

解法一通过在 for 循环里加入判断条件，让每一层不出现重复的元素的选择从而避免了结果的重复。

C++

解法一去重 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 会记录前一个元素是否被选中，当前一个元素选中，并且和当前的元素相同时，就不需要再次扩展这种情况了。如果没有这个变量的话，就没办法确定是否选择过这个元素，有可能会造成情况的遗漏。