This post is completed by 1 user

  • 0
 Add to List
Medium

457. 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.
  3. Start with currSum = 0, start = 0, combinationList=null
  4. Iterate through i = start to length(arrA[]).
    1. Add arrA[i] to currSum. 
    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.)

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]

Related Problems: