Combination Sum
You are given an array/list ARR of N distinct positive integers. You are also given a non-negative integer B.

Your task is to find all unique combinations in the array whose sum is equal to B. A number can be chosen any number of times from array/list ARR.

Elements in each combination must be in non-decreasing order.

For example:

Let the array ARR be [1, 2, 3] and B = 5. Then all possible valid combinations are- (1, 1, 1, 1, 1) (1, 1, 1, 2) (1, 1, 3) (1, 2, 2) (2, 3)

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows. Then the first line of each test case contains two space separated integers ‘N’ and ‘B’ denoting the number of elements in the array/list and the target sum respectively. The second line of each test case contains N space separated integers the elements of array/list ARR.

Output Format :

For each test case, print all possible valid combinations in separate lines. You can print combinations in any order. Elements in each combination must be in non-decreasing order. Output for each test case will be printed in a new line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Combination Sum

You are given an array/list ARR of N distinct positive integers. You are also given a non-negative integer B.

Your task is to find all unique combinations in the array whose sum is equal to B. A number can be chosen any number of times from array/list ARR.

Elements in each combination must be in non-decreasing order.

For example:

Let the array ARR be [1, 2, 3] and B = 5. Then all possible valid combinations are-

(1, 1, 1, 1, 1)
(1, 1, 1, 2)
(1, 1, 3)
(1, 2, 2)
(2, 3)

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

Then the first line of each test case contains two space separated integers  ‘N’ and ‘B’ denoting the number of elements in the array/list and the target sum respectively.

The second line of each test case contains N space separated integers the elements of array/list ARR.

Output Format :

For each test case, print all possible valid combinations in separate lines. You can print combinations in any order. Elements in each combination must be in non-decreasing order.

Output for each test case will be printed in a new line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 15
1 <= B <= 20
1 <= ARR[i] <= 20

Time Limit: 1sec

Accepted Answer

This problem can be solved using recursion.
Steps :
1. Sort the array in increasing order.
2. Next, remove all the duplicates from array.
3. Now, use recursion and backtracking
(A) If at any time sub-problem sum == 0 then insert that array to the result.
(B) Else if sum < 0 then ignore and return.
(C) Else insert the present index in that array to the current vector and call the function with sum = sum-arr[index] and index = index, then pop that element from current index (backtrack) and call the function with sum = sum and index = index+1

Accepted Answer

Recursive Approach

We can use a backtracking approach to generate all the valid combinations.

The approach will be:

We will sort the array/list ‘ARR’ in ascending order.
Let the current sum of the combination on which we are recursing over be ‘currSum’ and the index which we are on in the array/list ‘ARR’ be ‘currIndex’.
In each recursive call, we will:
- While currSum <= B:
  - Increase ‘currSum’ by ARR[currIndex].
  - Insert ‘ARR[currIndex]’ in ‘currList’.
  - Recurse over ‘currIndex’ + 1.
- We remove all ‘ARR[currIndex]’ inserted into ‘currList’ for backtracking.
The state where the ‘currSum’ is equal to B will be a valid combination and we will include it in our final answer.

Space Complexity: OtherExplanation:

O(N*2^N), where N denotes the number of elements of the array/list ‘ARR’.

The space complexity due to recursion stack will be O(2^N). For each possible state, we store all possible elements in ‘currList’. Hence, overall space complexity will be O(N*2^N).

Time Complexity: O(2^n)Explanation:

O(2^N), where N denotes the number of elements of the array/list ‘ARR’.

Since we are recursing over all possible combinations of the array ‘ARR’, the time complexity will be O(2^N).

Java (SE 1.8)

/*

    Time Complexity: O(2^N)

    Space Complexity: O(N*2^N)



    where 'N' is the total number of elements in the array.

*/



import java.util.*;



public class Solution {

    public static ArrayList> result;



    private static void solve(ArrayList currList, int currIndex, int currSum, int b, ArrayList arr) {

        if (currSum == b) 

        {

            result.add(new ArrayList(currList));

            return;

        }

        if (currIndex == arr.size()) 

        {

            return;

        }



        solve(currList, currIndex + 1, currSum, b, arr);



        int count = 0;



        while (currSum <= b) 

        {

            count++;



            currSum += arr.get(currIndex);



            currList.add(arr.get(currIndex));



            solve(currList, currIndex + 1, currSum, b, arr);

        }



        // We remove ARR[currIndex] from currList, 'count' number of times for backtracking

        while (count > 0) 

        {

            int index = currList.size() - 1;

            currList.remove(index);

            count--;

        }

    }



    public static ArrayList> combSum(ArrayList arr, int b) 

    {



        Collections.sort(arr);

        result = new ArrayList>();

        ArrayList currList = new ArrayList();

        solve(currList, 0, 0, b, arr);

        return result;

    }

}

Python (3.5)

'''

    Time Complexity: O(2^N)

    Space Complexity: O(N*2^N)



    where N is the total number of elements in the aray.

'''





from copy import copy



def solve(result, currIndex, currSum, currList, B, ARR):



    if currSum == B:

        result.append(copy(currList))

        return



    if currIndex == len(ARR):

        return 



    solve(result, currIndex + 1, currSum, currList, B, ARR)





    count = 0



    while currSum <= B:



        count += 1



        currSum += ARR[currIndex]



        currList.append(ARR[currIndex])



        solve(result, currIndex + 1, currSum, currList, B, ARR)





    ''' We remove ARR[currIndex] from currList, 'count'

       number of times for backtracking '''

    while count:

        currList.pop()

        count -= 1





def combSum(ARR, B):



    ARR.sort()

    

    result = []

    currList = []



    solve(result, 0, 0, currList, B, ARR)



    return result

C++ (g++ 5.4)

/*
    Time Complexity: O(2^N)
    Space Complexity: O(N*2^N)

    where N is the total number of elements in the aray.
*/


#include 


void solve(vector> &result, int currIndex, int currSum, 
			vector &currList, int B, vector &ARR)
{
	if (currSum == B)
	{
		result.push_back(currList);
		return ;
	}
	if (currIndex == ARR.size())
	{
		return ;
	}

	solve(result, currIndex + 1, currSum, currList, B, ARR);


	int count = 0;

	while (currSum <= B)
	{
		count++;

		currSum += ARR[currIndex];

		currList.push_back(ARR[currIndex]);

		solve(result, currIndex + 1, currSum, currList, B, ARR);
	}

	/* We remove ARR[currIndex] from currList, 'count'
	   number of times for backtracking */
	while (count--)
	{
		currList.pop_back();
	}
}


vector> combSum(vector &ARR, int B)
{
	sort(ARR.begin(), ARR.end());
	
	vector> result;

	vector currList;

	solve(result, 0, 0, currList, B, ARR);

	return result;
}