[Approach 1] Leetcode #39: Combination Sum

Leetcode_0039.cpp

class Solution {
public:
    vector<vector<int>> answer;
    vector<int> numbers;

    void recurse(vector<int> &path, int index, 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. 
            index >= numbers.size()) { // no more numbers left to select.
            return;
        }
        
        // There are only 2 possibilities - Either to consider/select the number
        // or not consider the number.
        
        // Possibility 1 - Don't consider the number at the current index.
        recurse(path, index+1, target); // move to next number.
        
        // Possibility 2 - Consider the number at current index.
        path.push_back(numbers[index]); // consider the number.
        recurse(path, 
                index, // same number can be used again, so don't change
                       // the index
                target-numbers[index]); // reduce the target.
        path.pop_back(); // undo the consideration.
    }
    
    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;
    }
};