-
Notifications
You must be signed in to change notification settings - Fork 8
Expand file tree
/
Copy pathcombination_sum.cpp
More file actions
103 lines (94 loc) · 3.45 KB
/
Copy pathcombination_sum.cpp
File metadata and controls
103 lines (94 loc) · 3.45 KB
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
93
94
95
96
97
98
99
100
101
102
103
/*a
* leetcode Question 17: Combination Sum
* Combination Sum
*
*
* Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
* The same repeated number may be chosen from C unlimited number of times.
* Note:
*
* All numbers (including target) will be positive integers.
* Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
* The solution set must not contain duplicate combinations.
*
* For example, given candidate set 2,3,6,7 and target 7,
* A solution set is:
* [7]
* [2, 2, 3]
*
* Analysis:
*
* Because the problem is to get all the possible results, not the best or the number of result, thus we don't need to consider DP(dynamic programming), DFS is enough to handle it.
*
* The idea is to scan from the first to the last element from the ordered array. check every possible combination of these numbers(multiple times for a single element).
*
* the end condition of the dfs function is
* 1. the target ==0 , print list, return
* 2. the target < 0 return
* 3. start position >= array size return
* otherwise, from for each element in the array, dfs(start, target-element value);
* details see the source code:
* */
class Solution {
public:
void dfs(vector<int>const &candidates, int target, vector<vector<int> > &res, vector<int> &r, int i){
if (target<0){
return;
}else{
if (target==0){
res.push_back(r);
}else{
while (i<candidates.size() && target-candidates[i]>=0){
r.push_back(candidates[i]);
dfs(candidates,target-candidates[i],res,r,i);
i++;
r.pop_back();
}
}
}
}
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int> > res;
if (candidates.size()==0){return res;}
sort(candidates.begin(),candidates.end());
vector<int> r;
dfs(candidates,target,res,r,0);
return res;
}
};
///version 2. no duplicattion from source
class Solution {
public:
void dfs(vector<int> &num, int target, vector<vector<int> > &res, vector<int> &r,int st){
if (target<0){
return;
}else{
if (target==0){
res.push_back(r);
}else{
int pre = -1;
for (int i=st;i<num.size();i++){
if (num[i]!=pre){
r.push_back(num[i]);
dfs(num,target-num[i],res,r,i+1);
pre = num[i];
r.pop_back();
}
}
}
}
}
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int> > res;
if (num.size()==0){return res;}
sort(num.begin(),num.end());
vector<int> r;
dfs(num,target,res,r,0);
return res;
}
};
Reviewed