去重操作在一些题目中会出现一个复杂的问题即当一个集合有重复元素时题目希望最终得到的结果集合不包含重复的元素。如果按照模板的做法就算每个元素只选择一次出现重复的选择仍然是不可避免的针对这样的问题上述的两种解法分别需要做不同的修改。解法一解法一通过在 for 循环里加入判断条件让每一层不出现重复的元素的选择从而避免了结果的重复。C解法一去重 class Solution { public: void backtrack(vectorvectorint ans, vectorint tmp, vectorint 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(); } } vectorvectorint combinationSum2(vectorint candidates, int target) { vectorvectorint ans; vectorint 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 会记录前一个元素是否被选中当前一个元素选中并且和当前的元素相同时就不需要再次扩展这种情况了。如果没有这个变量的话就没办法确定是否选择过这个元素有可能会造成情况的遗漏。