-
Notifications
You must be signed in to change notification settings - Fork 6
/
combination_sum.cpp
38 lines (28 loc) · 1.32 KB
/
combination_sum.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
class Solution {
/*
Based on general solution of backtracking - https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)
*/
private:
void backtrack(vector<vector<int>> &global_result, vector<int> &local_result, vector<int> &candidates, int start, int remaining) {
if(remaining < 0) return;
if(remaining == 0) {
global_result.push_back(local_result);
}
for(int i=start; i<candidates.size(); i++) {
local_result.push_back(candidates[i]);
//for backtracking remember to use i and not i+1 as reusing of elements is allowed
backtrack(global_result, local_result, candidates, i, remaining - candidates[i]);
local_result.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
if(candidates.size() == 0) return vector<vector<int>>();
vector<vector<int>> gr;
vector<int> lr;
sort(candidates.begin(), candidates.end());
// candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());
backtrack(gr, lr, candidates, 0, target);
return gr;
}
};