-
Notifications
You must be signed in to change notification settings - Fork 0
/
my_040_Combination SumII.cpp
39 lines (39 loc) · 1.19 KB
/
my_040_Combination SumII.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
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> out;
vector<vector<int>> result;
sort(candidates.begin(), candidates.end());
Sol(candidates, target, 0, out, result);
set<vector<int>> tmp;
tmp.insert(result.begin(), result.end());
result = {};
for (auto it : tmp)
result.push_back(it);
return result;
}
void Sol(vector<int>& candidates, int target, int level, vector<int>& out, vector<vector<int>>& result) {
int sum = Sum(out);
if (sum == target) {
result.push_back(out);
return;
}
if (sum < target) {
for (int i = level; i < candidates.size(); ++i) {
if (sum + candidates[i] > target)
break;
out.push_back(candidates[i]);
Sol(candidates, target, i + 1, out, result);
out.pop_back();
}
}
else
return;
}
inline int Sum(vector<int>& out) {
int sum = 0;
for (int i = 0; i < out.size(); ++i)
sum += out[i];
return sum;
}
};