# Combination Sum II

Posted: 28 Jan, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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
``````