# Combination Sum II

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

First**, **sort the given array in non-decreasing order, it will help to generate combinations in non-decreasing order. There will be 2 ^ N possible combinations of the given array, We** create** a vector ‘result’ and then we one by one check for all possible combinations, whether the sum of its elements is equal to ‘target’ or not. If the sum of the combination is equal to ‘target’, we will append it in vector ‘result’.

We finally sort vector ‘result’ in lexicographical order and remove all duplicates from it.

We can find all combinations of array both iteratively or recursively, Here, we will be using the iterative approach only.

**Algorithm**:

- Sort the given array ‘arr’.
- Create a vector ‘result’ It will keep all combinations having sum equal to ‘target’.
- Run a loop where ‘i’ ranges from 0 to 2^N-1, and in each iteration do the following -:
- Create an empty vector ‘comb’
- Run a loop where ‘j’ ranges from 0 to N - 1 and if ‘jth’ bit is set in ‘i’ then append element arr[j] in ‘comb’.
- If the sum of all elements of ‘comb’ is equal to ‘target’ then add it in vector ‘result’
- Sort the vector ‘result’
- Remove all duplicates from vector ‘result’. This can be done easily by either using built-in library functions or using the fact that duplicate entries are grouped together after sorting.

- Return ‘result’.

This problem can be solved using backtracking, The idea is to incrementally build combinations to the solution set, and abandon a combination ("backtrack") as soon as it determines that the combination cannot achieve the target sum. In order to avoid duplicates, we cannot consider each element separately. We need to consider a group of the unique integer while backtracking.

We first create an array ‘counters’ that will keep the frequency of each element in the array.

After that, we start from smallest to the largest unique integer in ‘arr’ and for each unique integer, we try to include each of its number of occurrence (from largest to smallest) in combination if it can lead to the target sum, otherwise backtrack to determine other such combinations. Note, the order i.e smallest to largest unique integer and largest to smallest in occurrence will ensure that combination will generate in lexicographical order.

**Algorithm:**

- This is a recursive approach.
- Iterate over the given array ‘arr’ and find the frequency of each unique element in that array, store these frequencies in array ‘counter’ such that ‘counter[i]’ gives the frequency of ith integer.
- We define a function ‘helper(comb, remain, curr, counter, result)’ where
- ‘comb’: the combination we built so far at each step
- ‘remain’: the remaining sum to reach the target sum.
- ‘curr’: current unique element.
- ‘counter’: Array having the frequency of each element.
- ‘result’: the final combinations that have the target sum.

- At each invocation of the backtrack function, we do the following -:
- If ‘remain’ is 0 then append the ‘comb’ in vector ‘result’ and return.
- If ‘curr' is greater than max element present in the array ‘arr’ then return.
- Run a while loop till ‘counter[curr]’ > 0 and ‘remain’ >= ‘curr’, in each iteration of this while loop append curr in array ‘comb’ and subtract curr from remain, after that decrement ‘counter[curr]’ by 1.
- Run a loop till all the occurrence of ‘curr’ is not removed from ‘comb’. In each iteration of this loop call ‘helper(comb, remain, curr+1, counter, result)’ and then increment ‘remain’ by ‘curr’. This will search for all valid combination form by using different groups of ‘curr’
- Call ‘helper(comb, remain, curr+1, counter, result)’ to search for all combinations that do not have integer ‘curr’.

- Return ‘result’.