Leetcode 39 : Combination Sum solution

Problem Statement could be found @ https://leetcode.com/problems/combination-sum/

Approach - Let us consider the example given in  problem statement itself.

input - [2, 3, 6, 7]
target - 7

Here, we have to consider each element multiple times so we will first start with 2
So, first we pick 2,2,2,2 then sum becomes 8, so noway picking 2 or any other number from input another time would give us desired target. And Hence we need to go back

Now, when we go back we have 2,2,2 and next number we pick up is 3.Again sum is 9,so we need to go back. Similarly, we pick  6 & 7 next. This step could have been optimized to short circuit at 2,2,2,2 itself, but here I'm not doing that much optimization.

Next we go back and have 2,2. Next number picked up is 3. So the sum becomes 7 which is desired . Hence we store it in output.

Points to consider
1. The input array may not be sorted so it is better to sort it initially
2. Since numbers are not negative, we can leverage on total sum being greater than target to stop
3. At every step we are almost doing the same step hence recursion can be used and point 2 can be used as terminating condition for recursion


Code Snippet-

class Solution {
    vector<vector<int>> retvec;
    vector<int> val;
    int target;
public:
void helper(int index, int sum, vector<int> &v){
   
    if (sum > target){
        return;
    }
   
    if ( sum == target){
        retvec.push_back(v);
        return;
    }
   
    for (int i=index;i<val.size();i++){
        v.push_back(val[i]);
        helper(i, sum+val [i],v);
        v.pop_back();
    }
}
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        this->target = target;
       
        val = candidates;
        sort(val.begin(), val.end());
        vector<int> v;
        helper(0,0,v);
        return retvec;
    }
};