# Given an array, print all unique subsets with a given sum.

Objective: Given an array of integers and number N, Write an algorithm to find and print all the subsets of the array for which sum is equal to N.

Example:

```input [] = {6,2,7,8,2,4,1,3,7,5}
Sum = 8
Output:
[1, 2, 2, 3]
[1, 2, 5]
[1, 3, 4]
[1, 7]
[2, 2, 4]
[2, 6]
[3, 5]
[8]

input [] = {1,2,3,4,5,6};
Sum = 6
[1, 2, 3]
[1, 5]
[2, 4]
[6]
```

Approach: Use Recursion

1. Given arrA[] and sum.
2. Sort the arrA[] in ascending order.
4. Iterate through i = start to length(arrA[]).
2. Put arrA[i] to combinationList.
3. Make a recursive call with start = start + 1 (to process next elements) and combinationList.
4. In tail recursion, backtrack and remove arrA[i] from the combinationList to find more solutions
5. Base case: if currSum=sum,  Print combinationList.
6. During iteration, if the current element is the same as the previous element then skip the current element. (this step is required to avoid duplicate results in case array has duplicate elements, sorting will bring them together so skip one of the element, for example, array is [1, 1, 4], sum = 5, then the results would be [1, 4] and [1, 4] if we use both the 1’s but it produces identical results, so consider only one element.)

Complete Code:

Output:

```Given Array: [6, 2, 7, 8, 2, 4, 1, 3, 7, 5], required sum: 8
[1, 2, 2, 3]
[1, 2, 5]
[1, 3, 4]
[1, 7]
[2, 2, 4]
[2, 6]
[3, 5]
[8]
```

__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________