|
This post is completed by 2 users
|
Add to List |
468. 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
- Given arrA[] and sum.
- Sort the arrA[] in ascending order.
- Start with currSum = 0, startIndex = 0, combinationList=null
- Iterate through i = startIndex to length(arrA[]).
- Add arrA[i] to currSum.
- 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.
Output:
Given Array: [2, 6, 3, 5], required sum: 8 [2, 2, 2, 2] [2, 3, 3] [2, 6] [3, 5]