Combination Sum | Recursion | Backtracking | C++

 

Problem Description:

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

 

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The combinations themselves must be sorted in ascending order.
• CombinationA > CombinationB iff (a1 > b1) OR (a1 = b1 AND a2 > b2) OR … (a1 = b1 AND a2 = b2 AND … ai = bi AND ai+1 > bi+1)
• The solution set must not contain duplicate combinations.

Example,
Given candidate set 2,3,6,7 and target 7,
A solution set is:

[2, 2, 3]
[7]

 

Warning : DO NOT USE LIBRARY FUNCTION FOR GENERATING COMBINATIONS.
Example : itertools.combinations in python.
If you do, we will disqualify your submission retroactively and give you penalty points.

 

Approach:

Since the problem is to get all the possible results, not the best or the number of result, thus we don’t need to consider DP(dynamic programming), recursion is needed to handle it.

We should use the following algorithm.

1. Sort the array(non-decreasing).
2. First remove all the duplicates from array.
3. Then use recursion and backtracking to solve 
   the problem.
   (A) If at any time sub-problem sum == 0 then 
       add that array to the result (vector of 
       vectors).
   (B) Else if sum if negative then ignore that 
       sub-problem.
   (C) Else insert the present array in that 
       index to the current vector and call 
       the function with sum = sum-ar[index] and
       index = index, then pop that element from 
       current index (backtrack) and call the 
       function with sum = sum and index = index+1 

Problem Solution in C++ Programming Language:

code:

void solve(vector<int> &A,vector<vector<int>> &sol,vector<int> curr,int B,int sum)

{   if(sum>B) return;

    if(sum==B)

    {

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

        for(auto x:sol)

        {

            if(x==curr) return;

        }

        sol.push_back(curr);

        return;

    }

    

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

    {

        if(sum+A[i]<=B)

        {

            curr.push_back(A[i]);

            solve(A,sol,curr,B,sum+A[i]);

            curr.pop_back();

        }

    }

    return;

}

vector<vector<int> > Solution::combinationSum(vector<int> &A, int B) 

{

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

    vector<vector<int>> sol;

    vector<int> curr;

    solve(A,sol,curr,B,0);

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

    return sol;

}

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Please share your reviews.

thanks for reading.👍😊

If you like the solution please share with your friends.

and for more dynamic programming question for interview preparation.