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.
  3. Start with currSum = 0, startIndex = 0, combinationList=null
  4. 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.

Complete Code:

Output:

Given Array: [2, 6, 3, 5], required sum: 8 
[2, 2, 2, 2] 
[2, 3, 3] 
[2, 6] 
[3, 5]
%d bloggers like this: