# Given an array, find all unique subsets with a given sum with allowed repeated digits.

Objective: Given an array of integers and number N, Write an algorithm to find and print all the unique subsets of array for which sum is equal to N where array elements can be repeated any number of times.

Example:

```int [] arrA={2,4,3}
sum =6
Output:
[2, 2, 2]
[2, 4]
[3, 3]

int [] arrA={2,6,3,5}
Sum = 8
[2, 2, 2, 2]
[2, 3, 3]
[2, 6]
[3, 5]
```

Approach: Use Recursion

1. Given arrA[] and sum.
2. Sort the arrA[] in ascending order.
4. Iterate through i = startIndex to length(arrA[]).
• Put arrA[i] to combinationList.
• Make a recursive call with startIndex (to process next elements) and combinationList.
• In tail recursion, backtrack and remove arrA[i] from the combinationList to find more solutions
• Base case: if currSum=sum,  Print combinationList.

Complete Code:

Output:

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

__________________________________________________
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.
__________________________________________________

#### You may also like...

This site uses Akismet to reduce spam. Learn how your comment data is processed.