-
Notifications
You must be signed in to change notification settings - Fork 0
/
combination_sum_2.cpp
44 lines (39 loc) · 1.17 KB
/
combination_sum_2.cpp
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
private:
vector<int> numbers;
int t;
void searchCombination(int begin, vector<vector<int> > &results, vector<int> &middleResult, int sum){
int len = numbers.size();
if(sum == t){
results.push_back(middleResult);
return;
}
for(int i = begin; i < len; i++){
if(i > begin && numbers[i] == numbers[i - 1]){
continue;
}
int s = sum + numbers[i];
if(s > t){
continue;
}
middleResult.push_back(numbers[i]);
searchCombination(i + 1, results, middleResult, s);
middleResult.pop_back();
}
}
public:
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
int len = num.size();
vector<vector<int> > results;
if(len <= 0){
return results;
}
numbers = num;
t = target;
sort(numbers.begin(), numbers.end());
vector<int> middleResult;
int sum= 0;
searchCombination(0, results, middleResult, sum);
return results;
}
};