-
Notifications
You must be signed in to change notification settings - Fork 14
/
combination-sum-ii.cpp
92 lines (83 loc) · 2.28 KB
/
combination-sum-ii.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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// 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]
// ]
//
//
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res = {};
vector<int> temp = {};
sort(candidates.begin(),candidates.end());
vector<int>v1(candidates);
backtrack(res, temp, candidates, target, 0);
return res;
}
void backtrack(vector<vector<int>>& result, vector<int>& temp, vector<int>& nums, int remain,int start) {
if (remain < 0) {
return;
}
else if (remain == 0) {
bool isDuplicate = false;
for (auto vs : result) {
if (vs.size() != temp.size()) {
continue;
}
else {
bool isAllSame = true;
for (int i = 0; i < vs.size(); i++) {
if (vs[i] != temp[i]) {
isAllSame = false;
break;
}
}
if (isAllSame) {
isDuplicate = true;
break;
}
}
}
if (!isDuplicate) {
vector<int> v1(temp);
result.push_back(v1);
}
}
else {
for (int i = start; i < nums.size(); i++) {
temp.push_back(nums[i]);
backtrack(result, temp, nums, remain - nums[i], i+1);
temp.pop_back();
}
}
}
};