Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
[Approach 2] Leetcode #39: Combination Sum
class Solution {
public:
vector<vector<int>> answer;
vector<int> numbers;
void recurse(vector<int> &path, int startIndex, int target) {
if (target == 0) { // no more numbers are required.
answer.push_back(path); // add current numbers into the answer.
return;
}
if (target < 0) { // invalid. we added more numbers than needed.
return;
}
for (int i=startIndex; i<numbers.size(); i++) { // for each possibility.
path.push_back(numbers[i]); // consider the possibility.
recurse(path,
i, // same number can be used again, so don't change
// the index.
target-numbers[i]); // reduce the target.
path.pop_back(); // undo the possibility.
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
numbers = candidates;
sort(numbers.begin(), numbers.end());
vector<int> path; // to store selected numbers. Initially empty.
recurse(path,
0, // what index to start from.
target); // how much sum to make.
return answer;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment