|
4 | 4 |
|
5 | 5 | Backtracking, generate all combo sums, push/pop + index checking to explore new combos |
6 | 6 |
|
7 | | - Time: O(n^target) |
| 7 | + Time: O(2^target) |
8 | 8 | Space: O(target) |
9 | 9 | */ |
10 | 10 |
|
11 | 11 | classSolution { |
12 | 12 | public: |
13 | 13 | vector<vector<int>>combinationSum(vector<int>& candidates,int target) { |
14 | | -sort(candidates.begin(), candidates.end()); |
15 | | - |
16 | | - vector<int> curr; |
17 | | - vector<vector<int>> result; |
18 | | - |
19 | | -dfs(candidates, target,0,0, curr, result); |
20 | | -return result; |
| 14 | + std::vector<int> curr; |
| 15 | + std::vector<std::vector<int>> res; |
| 16 | +helper(candidates, target,0, curr, res); |
| 17 | +return res; |
21 | 18 | } |
22 | 19 | private: |
23 | | -voiddfs(vector<int>&candidates,int target,intsum,int start,vector<int>& curr, vector<vector<int>>&result) { |
24 | | -if (sum > target) { |
| 20 | +voidhelper(std::vector<int>&cands,int target,inti, std::vector<int>& curr, std::vector<std::vector<int>>&res) { |
| 21 | +if (i >= cands.size() || target <0) |
25 | 22 | return; |
26 | | - } |
27 | | -if (sum ==target) { |
28 | | -result.push_back(curr); |
| 23 | + |
| 24 | +if (target ==0) { |
| 25 | +res.push_back(curr); |
29 | 26 | return; |
30 | 27 | } |
31 | | -for (int i = start; i < candidates.size(); i++) { |
32 | | - curr.push_back(candidates[i]); |
33 | | -dfs(candidates, target, sum + candidates[i], i, curr, result); |
34 | | - curr.pop_back(); |
35 | | - } |
| 28 | + |
| 29 | + curr.push_back(cands[i]); |
| 30 | + |
| 31 | +helper(cands, target - cands[i], i, curr, res); |
| 32 | + |
| 33 | + curr.pop_back(); |
| 34 | + |
| 35 | +helper(cands, target, i +1, curr, res); |
36 | 36 | } |
37 | 37 | }; |