Leetcode #40: Combination Sum II

Leetcode_0040.cpp

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; 
    }
};