4

Combination Sum II

Difficulty: MEDIUM
Contributed By
Arshit Babariya
Avg. time to solve
30 min
Success Rate
70%

Problem Statement

You are given an array ‘Arr’ of ‘N’ positive integers. You are also given a positive integer ‘target’.

Your task is to find all unique combinations of the array ‘Arr’ whose sum is equal to ‘target’. Each number in ‘Arr’ may only be used once in the combination.

Elements in each combination must be in non-decreasing order and you need to print all unique combinations in lexicographical order.

Note:
In lexicographical order, combination/array  ‘A’  comes before array ‘B’ if ‘A’ is the prefix of array ‘B’, or if none of them is a prefix of the other and at the first position where they differ integer in ‘A’ is smaller than the integer in ‘B’.
Example:
Let the array ‘Arr’ be [1, 2, 3, 1] and ‘target’ = 5. Then all possible valid combinations in lexicographical order are -:
(1, 1, 3)
(2, 3)
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases.

Then the first line of each test case contains two space-separated integers  ‘N’ and ‘target’ denoting the number of elements in ‘Arr’ and the ‘target'

The second line of each test case contains N space-separated integers the elements of array ‘Arr’.
Output Format:
For each test case, print all possible valid combinations in a separate line in the lexicographical order. Elements in each combination must be in non-decreasing order. Print a new line after each test case.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10 
1 <= N <= 20
1 <= Arr[i] <= 30
1 <= target <= 30

Time Limit: 1 sec
Sample Input 1:
2
7 8
10 1 2 7 6 1 5
5 2
1 1 1 1 1
Sample Output 1:
1 1 6
1 2 5
1 7
2 6

1 1
Explanation For Sample Input 1:
Test Case 1:

Here ‘N’ = 7, Arr = [10, 1, 2, 7, 6, 1 , 5], and ‘target’ = 8
All unique combinations whose sum of elements is 8 are -:     

(1, 1, 6)  because, 1 + 1 + 6 = 8
(1, 2, 5)  because,  1 + 2 + 5 = 8
(1, 7)  because, 1 + 7 = 8                                                                                                               
(2, 6)  because,  2 + 6 = 8

Note, elements in each combination are in non-decreasing order and all unique combinations are arranged in lexicographical order. 

Test Case 2:

All elements are 1 in a given array and ‘target’ = 2,  so the only possible combination is (1, 1) as 1 + 1 = 2
Sample Input 2:
2
5 5
1 2 3 1 5
1 3
3
Sample Output 2:
1 1 3
2 3
5

3
Reset Code
Full screen
copy-code
Console