LeetCode40. 组合总和 II

题目

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

分析

这个题目又是组合的变形。单集合求给定要求的组合，且该集合里的数字可能会重复，集合里的每个数字只能用一次，解集不能包含重复的组合。

对于给定集合里的数字可能会重复，这就意味着所得到的解集里面的组合可能会重复，要对解集去重。

对于给定集合里的数字只能使用一次，这就需要我们用startIndex来记录每次选数字的位置，并不是可以任意选。

代码

自己第一次所写

 1 class Solution {
 2 public:
 3     vector<int>path;
 4     vector<vector<int>>res;
 5     void backtracking(const vector<int>& candidates,int target,int sum,int startIndex){
 6         if(sum > target){
 7             return;
 8         }
 9         if(sum == target){
10             if(find(res.begin(),res.end(),path) == res.end()){ //在之前结果里面没找到
11                 res.push_back(path);
12             }
13             
14             return;
15         }
16         for(int i = startIndex;i < candidates.size() && sum + candidates[i] <= target;i++){
17             sum += candidates[i];
18             path.push_back(candidates[i]);
19             backtracking(candidates,target,sum,i+1);
20             sum -= candidates[i];
21             path.pop_back();
22         }
23     }
24     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
25         sort(candidates.begin(),candidates.end());
26         backtracking(candidates,target,0,0);
27         return res;
28     }
29 };

1. 终止条件依旧是 sum > target ，如果 sum == target 意味着找到了路径，但是这时能不能加入到结果里面呢？还不能直接加入结果，先要从结果数组中查找下是否有该结果，如果之前已经有该结果了，就不必再添加了。

2. 对于for 循环进入搜索的条件我加强了，目的是为了剪枝，提前进行判断下一层是否终止。要做到这一步需要提前对原始集合进行排序（25行）。

再进一步剪枝优化

上面虽然已经剪枝了部分，但还是没有最优，因为是每次得到path后查看之前是否有该结果。如果一开始就把重复的剪枝，这样就更优。解集里面出现重复的组合本质上搜索树的同层出现了重复，而同一分支上可以重复。那么如何判断搜索树的同一层次上的元素已经使用过了呢？开始我会想当然的说，只需要 candidates[i] == candidates[i-1] 即可，但仔细想想这样不对，因为如果只是这样的话就不能保留同一分支上出现重复的情况。如下，只满足这个宽泛的条件是不行的，因为这样就直接连带同一分支重复元素的情况包含在内了，符合条件的解集组合数量变少。

 for(int i = startIndex;i < candidates.size() && sum + candidates[i]<= target;i++){
            if(i > 0 && candidates[i] == candidates[i-1] /*&& used[i-1] == false*/)         continue;

最终：

candidates[i] == candidates[i - 1]相同的情况下：

used[i - 1] == true，说明同一树支candidates[i - 1]使用过
used[i - 1] == false，说明同一树层candidates[i - 1]使用过

最终代码

 1 class Solution {
 2 public:
 3     vector<int>path;
 4     vector<vector<int>>res;
 5     void backtracking(const vector<int>& candidates,int target,int sum,int startIndex,vector<bool>used){
 6         // if(sum > target){  可省略，因为for循环对其进行了剪枝
 7         //     return;
 8         // }
 9         if(sum == target){
10             res.push_back(path);
11             return;
12         }
13                  
14         for(int i = startIndex;i < candidates.size() && sum + candidates[i]<= target;i++){
15             if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false) continue;
16             sum += candidates[i];
17             path.push_back(candidates[i]);
18             used[i] = true;
19             backtracking(candidates,target,sum,i+1,used);
20             used[i] = false;
21             sum -= candidates[i];
22             path.pop_back();
23         }
24     }
25     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
26         vector<bool>used(candidates.size(),false);
27         sort(candidates.begin(),candidates.end());
28         backtracking(candidates,target,0,0,used);
29         return res;
30     }
31 };

本题我们学到通过开一个used数组来去重