Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode #40: Combination Sum II
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;
}
int previouslyChecked = -1;
for (int i=startIndex; i<numbers.size(); i++) { // for each possibility.
if (previouslyChecked == numbers[i]) { // skip if the number is
// the same as previous.
// Why skipping is the right thing to do?
// Remember that we are constructing a path.
// Path has already tried adding the number into it and
// recursively solving the problem. So there is no point in
// checking the same number again.
continue;
}
path.push_back(numbers[i]); // consider the possibility.
recurse(path,
i+1, // only consider numbers beyond i to avoid duplicates,
// otherwise {2, 3} and {3, 2} will both be added.
target-numbers[i]); // reduce the target.
path.pop_back(); // undo the possibility.
previouslyChecked = numbers[i]; // update previous.
}
}
vector<vector<int>> combinationSum2(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