Find unique combinations with sum B

Easy

0/40

Average time to solve is 15m

5 upvotes

Asked in company

Problem statement

Given a list of 'n' distinct positive integers and a non-negative integer 'B. Find the number of unique combinations possible from the elements of the list such that the sum of numbers in the combination is equal to 'B' . We can take an element from the list multiple times in our combination.

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)

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

Sample Output 1:

6 4
1 1 1 1 1 1 1 1 1 1
10

Sample Input 2 :

Sample Output 2:

5 
1 1 4 
1 1 1 1 1 1 
1 3 3 
1 1 1 1 3 
1 1 1 1 1 1 1

Approaches (1)

Approach 1

abcd

Time Complexity

Space Complexity

(100% EXP penalty)

Find unique combinations with sum B

Console