# [leetcode] Combination Sum II

### Combination Sum II

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

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

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set `10,1,2,7,6,1,5` and target `8`,
A solution set is:
`[1, 7]`
`[1, 2, 5]`
`[2, 6]`
`[1, 1, 6]`

```class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
vector<vector<int>> re;
vector<int> thisRe;
sort(num.begin(), num.end());
_combinationSum2(0, target, 0, num, thisRe,re);
return re;
}
void _combinationSum2(int sum, int target, int start, vector<int> &num, vector<int>& thisRe, vector<vector<int>>& re){
if(sum == target){
re.push_back(thisRe);
return ;
}
else if(start >= num.size()){
return ;
}
else{
for(int i = start; i < num.size();){
if(sum + num[i] > target){
break;
}
else{
thisRe.push_back(num[i]);
_combinationSum2(sum + num[i], target, i + 1, num, thisRe, re);
thisRe.pop_back();
}
while(++i < num.size() && num[i] == num[i - 1]){
;
}
}
}
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.