40. Combination Sum II 组合之和之二

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,

A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5,

A solution set is:
[
  [1,2,2],
  [5]
]

Difficulty: Medium

这道题和上道题Combination Sum 组合之和差不多,只是这里不能使用重复的数字. 这是需要在findSum递归的的时候传入i+1 以及需要在for循环的时候判断一下这个数和上一个数是否相等. 这样可以避免类似 {1,1,7} 8 这种输入,7的使用重复问题

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target){
        vector<vector<int>> res;
        vector<int> solution;
        sort(candidates.begin(), candidates.end());
        findSum2(candidates,0,target,solution,res);
        return res;
    }
    
    void findSum2(vector<int>& candidates,int start,int target,vector<int>& solution,vector<vector<int>>& res){
        if (target < 0) return;
        else if (target==0){
            res.push_back(solution);
        }else{
            for (int i = start;i < candidates.size();i++){
                if (i > start && candidates[i-1]==candidates[i]) continue;
                solution.push_back(candidates[i]);
                findSum2(candidates, i+1, target-candidates[i], solution, res);
                solution.pop_back();
            }
        }
    }
};
 
comments powered by Disqus