40. 组合总和 II

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

candidates 中的每个数字在每个组合中只能使用一次。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

该题为90. 子集 II的升级版

与上题相同的是，都要保证元素的非重复性，所以与上题使用set部分的代码是一致的。

区别在于在进行递归的过程中，需要随时对条件进行判断，只有满足等于target，才往result中添加。

并且在剪枝的时候，如果元素之和已经比target大，就没有必要进行下去了，直接退出即可。

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int> > result;
        vector<int> item;
        //去重所使用的集合
        set<vector<int>> item_set;
        //对nums进行排序。
        sort(candidates.begin(),candidates.end());
        putitem(0, candidates, result, item, item_set,target, 0);
        return result;
        
    }
    void putitem(int i, vector<int>& nums,vector<vector<int> > &result, vector<int> &item, set<vector<int>> &item_set,int target, int sum){
        if(i >= nums.size() || sum > target) return;
        
        sum += nums[i];
        item.push_back(nums[i]);
        //如果没有重复，就加入到最终的集合里。
        if(sum == target && item_set.find(item) == item_set.end()){
            result.push_back(item);
            //加入去重集合中。
            item_set.insert(item);
        }
        putitem(i+1, nums, result, item, item_set, target, sum);
        sum -= nums[i];
        item.pop_back();
        putitem(i+1, nums, result, item, item_set, target, sum);
    } 
};