This post is completed by 1 user

  • 0
 Add to List
Medium

419. Print all subsets of an array with a sum equal to zero

Objective: Given an array of integers write an algorithm to find all the subsets for which sum is equal to zero. The array contains both positive and negative integers.

Example:

Given Array: [8, 3, 5, 1, -4, -8], required sum: 0
Output:
[-8, -4, 1, 3, 8]
[-8, 3, 5]
[-8, 8]
[-4, 1, 3]


Given Array: [3, 1, -4, 2, 0], required sum: 0
Output:
[-4, 0, 1, 3]
[-4, 1, 3]
[0]

Approach:

  1. Given arrA[].
  2. Sort the arrA[] in ascending order.
  3. Start with currSum = 0, startIndex = 0, combinationList=null
  4. Iterate through i = startIndex to length(arrA[]).
    1. Add arrA[i] to currSum. 
    2. Put arrA[i] to combinationList.
    3. Make a recursive call with startIndex=i+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=0 and combinationList is not empty,  Print combinationList.

Output:

Given Array: [8, 3, 5, 1, -4, -8], required sum: 0
[-8, -4, 1, 3, 8]
[-8, 3, 5]
[-8, 8]
[-4, 1, 3]

Reference: https://www.careercup.com/question?id=6130274301640704

Related Problems: