• 1
of 1 vote

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
1
of 1 vote

Yet another solution:
Perform a recursive DFS - the element from an array can either be or not be in the set, hence the solution is O(2^N) time complexity. Pick one number with index 'i' and check the sum with number of index 'j>i', remember the sum. Pick a number with index 'k>j' and check the sum.... and so on and so forth, do this recursively for every combination.

The key point is to keep a track of a sequence of numbers in each recursive call. To achieve this one can use a single Stack. The number of elements on the stack corresponds on a depth of recursion. Once the elements on the stack sums to zero the stack is printed out. However, we still continue with the recursion.

A sample code is shown below:

``````private static Stack<Integer> stk;

public static void printSets(int[] a) {
stk = new Stack<Integer>();
printSets(a, 0, 0);
}

private static void printSets(int[] a, int hi, int sum) {
// Check the sum
if (sum == 0){
for (int y : stk)     // print the set
System.out.print(y+”, ”);
System.out.println();
}
// Recursion - cehck for every higher index
for (int k=hi; k<a.length-1; k++) {
int x = a[k];
stk.push(x);     // add to the stack
printSets(a, k+1, sum+x);
stk.pop();        // remove from the stack
}
}``````

Comment hidden because of low score. Click to expand.
0

I like the simplicity of this solution, but it doesn't seem to catch all cases.
I just ran it, and it only prints one set:

3, 1, -4,

Going to try to find where the problem is and attempt to get it working!

Comment hidden because of low score. Click to expand.
0

Got it working, thanks autoboli! See modified code down below.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is an NP-Complete problem so, well, it's going to be O(2^n) where n is the length of the subset. memory consumption will be O(n) too.

``````public static void printZeroSubsets(long[] set){
//used to prune branches that shouldn't be considered
//don't search further if the max or min value remaining cannot get the value back to 0
long max[] = new long[set.length];
long min[] = new long[set.length];
//a sort could speed up the branching with the additional max / min tracking
Arrays.sort(set);
int index = set.length -1;
if(set[index] > 0){
max[index] = set[index];
}
else{
min[index] = set[index];
}
for(int i = set.length -2; i > -1; i--){
if(set[i] > 0){
max[i] = max[i+1] + set[i];
min[i] = min[i+1];
}
else{
max[i] = max[i+1];
min[i] = min[i+1] + set[i];
}
}
Worker worker = new Worker(set, max, min);
worker.execute();
}

class Worker{
private long sum;
private long[] set;
private long[] max;
private long[] min;
StringBuilder b;

public Worker(long[] set, long[] max, long[] min){
this.set = set;
this.max = max;
this.min = min;
this.b = new StringBuilder();
}

public void execute(){
this.executeRecur(0, true);
}

private void executeRecur(int index, boolean notAdded){
//case being searched for
String str = this.b.toString();
System.out.println("{"+str+"}");
}
//normal search base case
if(index == this.set.length){
return;
}
//use the max / min tracking to stop branching early
if(this.sum > 0 && this.sum + this.min[index] > 0){
return;
}
else if(this.sum < 0 && this.sum + this.max[index] < 0){
return;
}
//search if this value was NOT included
this.executeRecur(index + 1);
//search if this value WAS included
int bLength = this.b.length();
this.sum += this.set[index];
if(bLength > 0){
this.b.append(',');
}
this.b.append(this.set[index]);
this.executeRecur(index + 1, true);
this.sum -= this.set[index];
this.b.setLength(bLength);
}
}``````

Comment hidden because of low score. Click to expand.
0

No longer stores solutions found so far by tracking whether they have been output already.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Bouncing off of this, i was thinking that maybe the following would optimize?

Sort list, from negative to positive. For each negative number, try all subsets of positive numbers that equal the negative number. For each positive number, try all subsets of negative numbers that equal the positive number.

Thus, instead of trying all possibilities, the run time becomes:

nlogn + m * 2^n + n * 2^m

such that:
n = # of negative numbers
m = # of positive numbers

assuming the list is balanced b/w positive and negative numbers, this can severely cut down running time to approximately peak at:

nlogn + 2^(n/2)/2 + 2^(n/2)/2 = nlogn + 2^(n/2), which is approximately 33millionish (bad for int, but good for long)

Comment hidden because of low score. Click to expand.
0

@Skorpius

But, assuming 'p' is the size of the entire set, either n or m could be roughly equivalent to p and your algorithmic complexity returns to O (2^p) which is the same thing as the original solution.

With the way the algorithm is already written, it will preform the optimization that you suggest (all the negative numbers are considered first but search branches that cannot be overcome by positive numbers are discarded). If you need to, follow some of the code by hand with a few trivial examples.

Comment hidden because of low score. Click to expand.
0

Being NP-complete doesn't imply complexity of O(2^n), it just implies exponential complexity. In fact, this problem has a fairly well-known O(2^(n/2)) algorithm.

Comment hidden because of low score. Click to expand.
0

@anonymous

O (2 ^ (n / 2 ) ) = O (2 ^ n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

For couples I propose the following:
1) Sort the keys, if the keys are comparables, use some sort O(N log N), if the keys are integers you may consider radix sort O(N)
2) Use two pointers 'left' and 'right' and set lef toi the first elem of the array, the latter on to the end of array.
3) Check if the sum is zero, YES -> add to the set, increase 'left', decrease 'right', NO -> cehck if sum is greather than zero. If yes do 'right--' otherwise 'left++'

The procedure on sorted array is O(N) hence, depending on sort implemetation, the solution is either O(N) or O(N log N)

A sample code for integers is below:

``````public static List<Integer[]> findCouples(int[] a) {
My.sort(a); 		// radix sort or compare-based sort (merge sort)

int i = 0; int j = a.length-1;
while(i<j) {
int x = a[i];
int y = b[j];
if (x+y == 0){
i++;
j--;
}
else if (x+y > 0) 	j--;
else                i++;
}
return out;
}``````

Now, the question is how to extend it to something else then couples. For sum of 3 the scanning on already sorted array will be O(N^2).

Comment hidden because of low score. Click to expand.
0

This is not 'find the pair that equals 0'. This is 'find all subsets that equal 0'. Yes, you answered the couples well, but when you move to more than a pair, you have do something like binary tree traversal.

Comment hidden because of low score. Click to expand.
0

You are right. I was thinkig of some generalization of 2-sum problem. Maybe it is not even possible as you mentioned.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my first attempt, but seems simple solution:
create a class which will have a list, sum of the items in list and initial Value.

a method to push an item into the list and a method to check if the list satisfies our condition(sum is zero).

``````import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ListAndSum{

List<Integer> list = new ArrayList<Integer>();
Integer initialValue;
Integer sum ;

public ListAndSum(Integer item){
setInitialValues(item);
}

public void setInitialValues(Integer item){
list.clear();
sum =item;
initialValue = item;
}

public Set<Integer> getListAsSetIfSatisFied(){
Set<Integer> result = null;
if(this.sum == 0){
result = new HashSet<Integer>(this.list);
setInitialValues(initialValue);
}

return result;
}

public boolean push(Integer item){
boolean result = false;
if(this.sum + item <= 0 && this.sum + item > initialValue){
this.sum = this.sum + item;
result = true;
}

return result;
}

}``````

Now use the above class for creating sets of sum zero comments are there in code.
Just Copy the above code in one file and copy the below code in another... it should work(not tested for all condition)

``````import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SetOfSumZero {

public static void main(String args[])throws Exception{

List<ListAndSum> sumZeroList = new ArrayList<ListAndSum>();
int array[] = {8,3,5,1,-4,-8, 0, 0 , 0,};
List<Set<Integer>> result = new ArrayList<Set<Integer>>();

for(int i=0; i<array.length;i++){
if(array[i] < 0){										// negative values initially
}else if(array[i] == 0){								// for already 0's in array, put them directly into the result
List<Integer> listItem = new ArrayList<Integer>();
}
}

for(int i=0; i<array.length;i++){
if(array[i] > 0){										// put only positive values as we want the sum to be 0
ListAndSum las = null;
for(int j=0 ; j<sumZeroList.size();j++){
las =sumZeroList.get(j);
System.out.println("    work for list: " + las.list);
if(las.push(array[i])){							// push won't work and return false if the value will increase the sum from 0 or decrease from its initial value
sumZeroList.set(j, las);
Set<Integer> satisFiedSet = las.getListAsSetIfSatisFied();
if(null != satisFiedSet){					// after pushing, if the list is satisfied, put it into result.
}
}
}
}
}

System.out.println("Results: ");

for(Set<Integer> s: result){
System.out.println(s);
}

}
}``````

Comment hidden because of low score. Click to expand.
0

i know the code is messy and can be optimized a lot. Idea here is:
1.) take 0's in result directly.
2.) take all negative values list.
3.) try putting every positive value to the above created list, untill it tends to 0.
4.) when the sum of initally negative value and all positive values become 0, set the list to initial position again(to get another set from same negative value if exist).

I think the only problem with my code is when there is multiple -ve value sums up to become one positive value or sum of positive values.
In that case the above program can be run for initial positive values and adding negative values.

i think map with a good hash function can solve the problem too.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{

public static void printSubsetOfSumZero(int[] a)
{
Arrays.sort(a);

int sum;
StringBuilder sb = new StringBuilder();

for(int i=0;i<a.length;i++)
{
sb.setLength(0);
sum = a[i];
sb.append(a[i]);

for( int j=a.length-1;j>=0;j--)
{

if(a[j]>0)
{

if((sum+a[j]) <= 0)
{
sum = sum + a[j];
sb.append(","+a[j]);
}
else
{
continue;
}
}
else
{
break;
}

if(sum == 0)
{
sum = a[i];
System.out.println(sb.toString());
sb.setLength(2);
}
}
}
}

public static void main (String[] args) throws java.lang.Exception
{
int a[] ={8,3,5,1,-4,-8};
printSubsetOfSumZero(a);
}
}``````

Comment hidden because of low score. Click to expand.
0

Isn't it gonna fail on {-1, 1, -7, 7} ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void printZeroSubsets(int[] array)
{
if (array != null)
{
printZeroSubsets(array, new boolean[array.length], 0, 0);
}
}

private static void printZeroSubsets(int[] array, boolean[] selected, int i, int sum)
{
if (i >= array.length)
{
if (sum == 0)
{
printSubset(array, selected);
}
}
else
{
printZeroSubsets(array, selected, i + 1, sum);
selected[i] = true;
printZeroSubsets(array, selected, i + 1, sum + array[i]);
selected[i] = false;
}
}

private static void printSubset(int[] array, boolean[] selected)
{
boolean f = false;
for (int i = 0; i < array.length; i++)
{
if (selected[i])
{
if (f)
{
System.out.print(", ");
}
System.out.print(array[i]);
f = true;
}
}
System.out.println();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

It's simple for pairs.

``````public struct Result
{
public long x, y;
public Result(long x, long y)
{
this.x = x;
this.y = y;
}

}
static long[] input = new long[]{8,3,5,1,-4,-8,4};
static List<Result> ans = new List<Result>();
static void Main(string[] args)
{
int end;
for (int start=0;start<input.Length-1;start++)
{
end = start + 1;
do
{
if (input[start] + input[end++] == 0) ans.Add(new Result(input[start], input[end-1]));
} while (end!=input.Length);

}
foreach (Result item in ans)
{
Console.WriteLine(item.x+" "+item.y);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The easiest hardcoded solution for 3-value subsets:

``````class Program
{
public struct Result
{
public long x, y, z;
public Result(long x, long y, long z)
{
this.x = x;
this.y = y;
this.z = z;
}

}
static long[] input = new long[]{8,3,5,1,-4,-8};
static List<Result> ans = new List<Result>();
static void Main(string[] args)
{
for (int i = 0; i < input.Length; i++)
{
for (int j = 0; j < input.Length; j++)
{
for (int k = 0; k < input.Length; k++)
{
//skip repeated combinations
if (j > i || k > j || k > i) continue;
//check out unique indexes and zero sums
if (i != j && i != k && j != k && (input[i] + input[j] + input[k] == 0))

}
}
}

foreach (Result item in ans)
{
Console.WriteLine(item.x+" "+item.y+" "+item.z);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void getAllSubsetsZero (vector<int>& set, vector<vector<int> >& zerosubsets) {
vector<vector<int> >& allsubsets
vector<int> empty;
allsubsets.push_back(empty);
allsubsets.push_back(set[0]);

for (int i=1; i<set.size(); i++) {
vector<vector<int> > tmpsubsets = allsubsets;
for (int j=0; j<tmpsubsets.size(); j++) {
tmpsubsets[j].push_back(set[i]);
int sum = 0;
for (int k=0; k<tmpsubsets[j].size(); k++) {
sum += tmpsubsets[j][k];
}
if (sum == 0 && tmpsubsets[j].size() > 0) {
zerosubsets.push_back(tmpsubsets[j]);
}
}
for (int j=0; j<tmpsubsets.size(); j++) {
allsubsets.push_back(tmpsubsets[j]);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

is it not same as partition subset sum problem?

Comment hidden because of low score. Click to expand.
0

Solution using recursion wou.edu/~broegb/Cs345/SubsetSum.pdf

``````int result[6];
void sum_zero(int a[], int i, int partial_sum, int target, int size)
{
result[i] = 1;
if (a[i] + partial_sum == target) {
int i;
for (i=0;i<SIZE(result);i++)
printf("%d\n", result[i] == 1?a[i]:0);
printf("\n\n");
result[i] = 0;
return;
} else if ((i+1 <= size ) && (a[i] + partial_sum <= target)) {
sum_zero(a, i+1, partial_sum+a[i], target, size);
}
result[i] = 0;
if ((i+1 <= size) && (a[i+1] + partial_sum <= target)) {
sum_zero(a, i+1, partial_sum, target, size);
}
}

int main()
{
int i;
int a[] = {8, 3, 5, 1, 4, 8};
sort(a, 0, SIZE(a)-1);
for (i=0;i<SIZE(result);i++)
printf("%d\n", a[i]);
printf("\n\n");
sum_zero(a, 0, 0, 9, SIZE(a));
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution without recursion. It uses a binary count/mask to choose which elements are considered for the sum. It's O(2^n), same as NP-hard subset sum problem.

``````#include <stdio.h>
#include <vector>
using namespace std;

bool TryInc(vector<int> &v) {
int carry = 1;
for (auto &e : v) {
e += carry;
carry = (e > 1);
e %= 2;
}
return carry == 0;
}

void FindSubsetSumZero(const vector<int> &v) {

// calculate sum
int sum = 0;
for (size_t i = 0; i < v.size(); ++i)
sum += (mask[i] ? v[i] : 0);

// print if found
if (sum == 0) {
for (size_t i = 0; i < v.size(); ++i)
printf("%d ", v[i]);
printf("\n");
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This will work :

``````input = [ 2, 1, -1, 0, 2, -1, -1 ]
map = {}
for num in input :
newMap = {num:[[num]]}
for key in map :
newListOfLists = []
for list1 in map[key] :
newListOfLists.append(list1[:] + [num] )
newMap[key+num] =  newListOfLists + ( newMap[key+num] if key+num in newMap else [] )
for key in newMap :
map[key] = newMap[key] + ( map[key] if key in map else [] )
print map[0]``````

The approach is same as that of others, i.e. finding subsets.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Sort the numbers
2. Construct a BST.
3. Now print all the paths which sum to a given value. Note the path can start and end anywhere in the tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it's a pretty decent solution:

``````public class SubsetsSumsZero {

public static Set<String> solution = new HashSet<String>();

public static void sumsZero(long[] list) {
Set<Long> sublist = new HashSet<Long>();
Set<Integer> positions = new HashSet<Integer>();
double aqumulated = 0;
sumsZeroRecursive(list, sublist, positions, aqumulated);

for (String combination: solution) {
System.out.println(combination);
}
}

public static void sumsZeroRecursive(long[] list , Set<Long> sublist, Set<Integer> positions, double aqumulated) {
for (int i = 0; i < list.length; i++) {
if (!positions.contains(i)) {
aqumulated += list[i];
checkSum(aqumulated, sublist);
sumsZeroRecursive(list, sublist, positions, aqumulated);
aqumulated -= list[i];
positions.remove(i);
sublist.remove(list[i]);
}
}
}

private static void checkSum(double aqumulated, Set<Long> sublist) {
if (aqumulated == 0) {
}
}

public static void main(String[] args) {
long[] list = new long []{8, 3, 5, 1, -4, -8, 0};
sumsZero(list);
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it's a pretty decent solution:

{{ {public class SubsetsSumsZero {

public static Set<String> solution = new HashSet<String>();

public static void sumsZero(long[] list) {
Set<Long> sublist = new HashSet<Long>();
Set<Integer> positions = new HashSet<Integer>();
double aqumulated = 0;
sumsZeroRecursive(list, sublist, positions, aqumulated);

for (String combination: solution) {
System.out.println(combination);
}
}

public static void sumsZeroRecursive(long[] list , Set<Long> sublist, Set<Integer> positions, double aqumulated) {
for (int i = 0; i < list.length; i++) {
if (!positions.contains(i)) {
aqumulated += list[i];
checkSum(aqumulated, sublist);
sumsZeroRecursive(list, sublist, positions, aqumulated);
aqumulated -= list[i];
positions.remove(i);
sublist.remove(list[i]);
}
}
}

private static void checkSum(double aqumulated, Set<Long> sublist) {
if (aqumulated == 0) {
}
}

public static void main(String[] args) {
long[] list = new long []{8, 3, 5, 1, -4, -8, 0};
sumsZero(list);
}
}}} }

Comment hidden because of low score. Click to expand.
0
of 0 vote

bool search_number(int* v,int number,int start,int en)
{
int e=en;
int MID=(start+e)/2;
while(start<=e)
{
if(number == v[MID])
{
return true;
}
else if(number < v[MID])
{
e=MID-1;
}
else
{
start=MID+1;
}
MID=(start+e)/2;
}
return false;
}

int main()
{
int v[] = {8,3,5,1,-4,-8};
std::sort(v,v+(sizeof(v)/sizeof(int)));
for(int i=0; i<(sizeof(v)/sizeof(int)); ++i)
cout<<v[i]<<endl;
int *frptr=v;
int *lstptr=v + (sizeof(v)/sizeof(int))-1;
int lstpos=(sizeof(v)/sizeof(int))-1;
int POS=0,MID=(sizeof(v)/sizeof(int))/2-1;
while(MID <= 0 || MID >= (sizeof(v)/sizeof(int)))
{
if(v[MID] < 0 && v[MID+1] > 0)
break;
else if(v[MID] > 0)
MID--;
else
MID++;

}
while(*frptr <= *lstptr)
{
if(*frptr + *lstptr == 0)
{
//found
cout<<"("<<*frptr<<","<<*lstptr<<")"<<endl;
lstptr--;
lstpos--;
}
else if(*frptr + *lstptr < 0)
{
if((*frptr + *lstptr)*-1 >= *lstptr)
{
frptr++;
lstptr=v + (sizeof(v)/sizeof(int))-1;
lstpos=(sizeof(v)/sizeof(int))-1;
}
else{
if (search_number(v,(*frptr + *lstptr)*-1,MID,lstpos))
cout<<"("<<*frptr<<","<<*lstptr<<","<<*frptr + *lstptr<<")"<<endl;
lstptr--;lstpos--;
}
}
else
{
lstptr--;lstpos--;
}

}
}

Comment hidden because of low score. Click to expand.
0

{{
#include<iostream>
#include <algorithm>

using namespace std;

bool search_number(int* v,int number,int start,int en)
{
int e=en;
int MID=(start+e)/2;
while(start<=e)
{
if(number == v[MID])
{
return true;
}
else if(number < v[MID])
{
e=MID-1;
}
else
{
start=MID+1;
}
MID=(start+e)/2;
}
return false;
}
int main()
{
int v[] = {8,3,5,1,-4,-8};
std::sort(v,v+(sizeof(v)/sizeof(int)));
for(int i=0; i<(sizeof(v)/sizeof(int)); ++i)
cout<<v[i]<<endl;
int *frptr=v;
int *lstptr=v + (sizeof(v)/sizeof(int))-1;
int lstpos=(sizeof(v)/sizeof(int))-1;
int POS=0,MID=(sizeof(v)/sizeof(int))/2-1;
while(MID <= 0 || MID >= (sizeof(v)/sizeof(int)))
{
if(v[MID] < 0 && v[MID+1] > 0)
break;
else if(v[MID] > 0)
MID--;
else
MID++;

}
while(*frptr <= *lstptr)
{
if(*frptr + *lstptr == 0)
{
//found
cout<<"("<<*frptr<<","<<*lstptr<<")"<<endl;
lstptr--;
lstpos--;
}
else if(*frptr + *lstptr < 0)
{
if((*frptr + *lstptr)*-1 >= *lstptr)
{
frptr++;
lstptr=v + (sizeof(v)/sizeof(int))-1;
lstpos=(sizeof(v)/sizeof(int))-1;
}
else{
if (search_number(v,(*frptr + *lstptr)*-1,MID,lstpos))
cout<<"("<<*frptr<<","<<*lstptr<<","<<*frptr + *lstptr<<")"<<endl;
lstptr--;lstpos--;
}
}
else
{
lstptr--;lstpos--;
}

}
}

}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the number of all subsets first; 2^n where n is the size of the array. Then think in binary: start from zero to 2^n-1 and check for the bit positions. 2^n-1 has n 1's in binary. Loop from 0 to 2^n-1, print the numbers in the array when there is a 1 in the counter at this position of the array where the sum of them is zero:

n = 6 (size of the array)
2^n = 64 (size of all possible subsets)

loop from zero to 2^n-1
start = 000000
end = 111111

Example: When counter is 33
array : 8, 3, 5, 1,-4,-8
counter: 1 0 0 0 0 1 (33)
counter: 0 1 1 0 0 1 (25)

Time complexity is: O(2^n)
Space complexity: O(n)

Python solution is here:

``````def findZeroSets(array):
subsetSize = 2**len(array)

for counter in range(subsetSize):
subset = []
sm = 0
for i in range(0, len(array)):
if (1<<i) & counter:
subset.append(array[i])
sm += array[i]

if len(subset) and sm == 0:
print subset

array = [8, 3, 5, 1, -4, -8]
findZeroSets(array)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.Stack;

class SubsetSumZero {
public static void main (String [] args) {
int [] set = {8, 3, 5, 1, -4, -8, 0};
Stack<Integer> tracker = new Stack<Integer>();
int runningSum = 0;
DFS(0, set, runningSum, tracker);
}

public static void DFS(int index, int[] array, int runningSum, Stack<Integer> tracker) {
if (index == array.length) {
if (runningSum == 0 && tracker.size() > 0) {
System.out.println("Subset = " + tracker);
}
return;
}
tracker.push(array[index]);
DFS(index + 1, array, runningSum + array[index], tracker);
tracker.pop();
DFS(index + 1, array, runningSum, tracker);
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Variation on what autoboli posted, this seems to work, it even got one more set that's not included in the answer.

Output from the code below is:
( -8 -4 1 3 8 )
( -8 3 5 )
( -8 8 )
( -4 1 3 )

``````/*
Print all subset of a given set which sums up to ZERO
{8,3,5,1,-4,-8}
so ans will be : {8,-8}
{3,5,-8}
{3,1,-4}
*/

import java.util.*;

public class SubsetSumZero
{
private static Stack<Integer> stk;

public static void printSets(int[] a) {
stk = new Stack<Integer>();

Arrays.sort(a);
printSets(a, 0, 0);
}

private static void printSets(int[] a, int hi, int sum) {
// Check the sum
if (sum == 0 && hi > 0){
// print the set
System.out.print("( ");
for (int y : stk){
System.out.print(y + " ");
}
System.out.println(" )");
}

// Recursion - check for every higher index
for (int k=hi; k < a.length; k++) {
int x = a[k];
stk.push(x);     // add to the stack
printSets(a, k+1, sum+x);
stk.pop();        // remove from the stack

}
}

public static void main(String[] args)
{
int[] array = {8,3,5,1,-4,-8};
printSets(array);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Variation on what autoboli posted, this seems to work, it even got one more set that's not included in the answer.

Output from the code below is:
( -8 -4 1 3 8 )
( -8 3 5 )
( -8 8 )
( -4 1 3 )

``````/*
Print all subset of a given set which sums up to ZERO
{8,3,5,1,-4,-8}
so ans will be : {8,-8}
{3,5,-8}
{3,1,-4}
*/

import java.util.*;

public class SubsetSumZero
{
private static Stack<Integer> stk;

public static void printSets(int[] a) {
stk = new Stack<Integer>();

Arrays.sort(a);
printSets(a, 0, 0);
}

private static void printSets(int[] a, int hi, int sum) {
// Check the sum
if (sum == 0 && hi > 0){
// print the set
System.out.print("( ");
for (int y : stk){
System.out.print(y + " ");
}
System.out.println(" )");
}

// Recursion - check for every higher index
for (int k=hi; k < a.length; k++) {
int x = a[k];
stk.push(x);     // add to the stack
printSets(a, k+1, sum+x);
stk.pop();        // remove from the stack

}
}

public static void main(String[] args)
{
int[] array = {8,3,5,1,-4,-8};
printSets(array);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

get all the subsets, verity them

``````Class SubsetToZero{

public void subsetToZero(int[] nums){

if(nums == null || nums.length == 0)
return;

List<List<Integer>> result = new ArrayList<List<Integer>>();

Arrays.sort(nums);  //sort array

for(int i = 0 ; i < nums.length ; i++){
List<List<Integer>> temp = new ArrayList<List<Integer>>();

for(List<Integer> list : result)

//add new element to every list
for(List<Integer> list : temp)

List<Integer> single = new ArrayList<Integer>();

//assgin to result
}

//test all subset to see if it is zero
for(int i = 0 ; i < result.size() ; i++){
List<Integer> list = result.get(i);
if(sum(list) == 0)
print(list);
}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Sum
{

private int[] A = new int[]{1,5,8,9,-5,-1,-3,2};

private boolean[] state = new boolean[A.length];;

public static void main(String[] args)
{
new Sum().getZeroSums(0, 0);
}

public void getZeroSums(int sum, int i)
{
if(i == A.length )
{
if(sum == 0)
{
for (int j = 0; j < state.length; j++)
{
if( state[j] )
System.out.print(A[j] + ", ");
}
System.out.println();
}
}
else
{
getZeroSums(sum, i + 1);
state[i] = true;
getZeroSums(sum + A[i], i + 1);
state[i] = false;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Sum
{

private int[] A = new int[]{1,5,8,9,-5,-1,-3,2};

private  boolean[] state = new boolean[A.length];;

public static void main(String[] args)
{
new Sum().getZeroSums(0, 0);
}

public void getZeroSums(int sum, int i)
{
if(i == A.length )
{
if(sum == 0)
{
for (int j = 0; j < state.length; j++)
{
if( state[j] )
System.out.print(A[j] + ", ");
}
System.out.println();
}
}
else
{
getZeroSums(sum, i + 1);
state[i] = true;
getZeroSums(sum + A[i], i + 1);
state[i] = false;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

output should include {-8, -4, 1, 3, 8} as well?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple recursive solution in C. It is 2^n. This will work for any targe sum value:

``````#include <stdio.h>
#include <stdlib.h>

void printArray(int *array, int size) {
for (int i = 0; i<size; i++) {
printf("%d ", array[i]);
}
printf("\n");
}

void print_all_subsets(int *nums, int numsSize, int start, int sum, int *subset, int subsetSize) {
if (numsSize == 0) {
printf("Empty set");
}
if (start >= numsSize) {
return;
}
// do not include element nums[start] in the subset
print_all_subsets(nums, numsSize, start+1, sum, subset, subsetSize);
// inlcude element nums[start] in the subset
subset[subsetSize++] = nums[start];
if (nums[start] == sum) { //found a subset
printArray(subset, subsetSize);
}
print_all_subsets(nums, numsSize, start+1, sum-nums[start], subset, subsetSize);

}

int* initArray(int size) {
int *array = (int*)calloc(size, sizeof(int));
return array;
}

int main() {
int nums[]={8, 3, 5, 1, -4, -8};
int numsSize = 6;
int *subset = initArray(numsSize);
int sum = 0;

print_all_subsets(nums, numsSize, 0, sum,  subset, 0);
free(subset);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's some STL code:

``````#include <vector>
#include <iostream>
using namespace std;

void PrintSubSets(const vector<int> & array, size_t start, vector<int> & subset, size_t subindex, int sum)
{
//
// Removing the sum == 0 prints all possible subsets
//

if (subindex > 0 && sum == 0)
{
cout << "{";
for (size_t i = 0; i < subindex; i++)
{
cout << subset[i] << " ";
}
cout << "}" << "\n";
}

for (size_t i = start; i < array.size(); i++)
{
subset[subindex] = array[i];
PrintSubSets(array, i + 1, subset, subindex + 1, sum + subset[subindex]);
}
}

// Driver program to test above functions
int main()
{
vector<int> V = { 0, 2, -2, 3, -3, 4, 5, 6, -15 };
PrintSubSets(V, 0, vector<int>(V.size()), 0, 0);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Test

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's some STL code:

``````#include <vector>
#include <iostream>
using namespace std;

void PrintSubSets(const vector<int> & array, size_t start, vector<int> & subset, size_t subindex, int sum)
{
// Remove the sum == 0 condition to print all subsets
if (subindex > 0 && sum == 0)
{
cout << "{";
for (size_t i = 0; i < subindex; i++)
{
cout << subset[i] << " ";
}
cout << "}" << "\n";
}

for (size_t i = start; i < array.size(); i++)
{
subset[subindex] = array[i];
PrintSubSets(array, i + 1, subset, subindex + 1, sum + subset[subindex]);
}
}

// Driver program to test above functions
int main()
{
vector<int> V = { 0, 2, -2, 3, -3, 4, 5, 6, -15 };
PrintSubSets(V, 0, vector<int>(V.size()), 0, 0);
return(0);
}``````

The Python code is even more compact :):

``````def PrintSubSets(array, index, subset, subindex, sum):
if subindex > 0 and sum == 0:
print subset[:subindex]

while index < len(array):
subset[subindex] = array[index]
PrintSubSets(array, index+1, subset, subindex+1, sum+subset[subindex])
index +=1

test = [0, 2, -2, 3, -3, 4, 5, 6, -15]
PrintSubSets(test, 0, [0]*len(test), 0, 0)``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````#include<stdio.h>
#include<conio.h>
int main()
{long int a[6];
int i,j,k,l,n,m,o;
printf("enter the array size=");
scanf("%d",&n);
printf("enter the array elements\n");
for(i=0;i<n;i++)
{scanf("%d",&a[i]);
}
printf("The subsets are:\n");
for(j=0;j<n;j++)
{
for(k=j+1;k<n;k++)
{
for(m=k+1;m<n;m++)
{
if((a[j]+a[k]+a[m])==0)
printf("{%d,%d,%d}\n",a[j],a[k],a[m]);
continue;
}
if(a[j]+a[k]==0)
printf("{%d,%d}\n",a[j],a[k]);
continue;
}
}

getch();
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

Only finds subsets of length 2 and 3

Comment hidden because of low score. Click to expand.
0

yeah i m improving it tobi..

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.