[Approach 2] Leetcode #39: Combination Sum

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