GeeksForGeeks Combination Sum, C++, 0.53 execution time

Question Link - https://practice.geeksforgeeks.org/problems/combination-sum-1587115620/1#

 void Sum(vector<vector<int>> &ans, vector<int> curr, vector<int> &A, int index, int target)

{

    if(target == 0)

    {

        ans.push_back(curr);

        return;

    }

    

    for(int i = index; i < A.size(); i++)

    {

        if(target - A[i] >= 0)

        {

            target -= A[i];

            curr.push_back(A[i]);

            

            Sum(ans, curr, A, i, target);

            

            target += A[i];

            curr.pop_back();

        }

    }

}

vector<vector<int> > combinationSum(vector<int> &A, int B) {

    // Your code here

    

    sort(A.begin(), A.end());

    A.erase(unique(A.begin(), A.end()), A.end());

    

    vector<vector<int>> ans;

    vector<int> curr;

    

    Sum(ans, curr, A, 0, B);

    

    return ans;

}

Offers