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.

Complete Code:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

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

%d bloggers like this: