Amazon Interview Question Dev Leads Dev Leads
Country: India
Interview Type: Written Test
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!
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
if(this.sum == 0 && notAdded){
String str = this.b.toString();
System.out.println("{"+str+"}");
notAdded = false;
}
//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);
}
}
No longer stores solutions found so far by tracking whether they have been output already.
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)
@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.
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.
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)
List<Integer[]> out = LinkedList<Integer[]>();
int i = 0; int j = a.length-1;
while(i<j) {
int x = a[i];
int y = b[j];
if (x+y == 0){
out.add(new int[] {x, y});
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).
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.
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();
list.add(item);
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;
this.list.add(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
sumZeroList.add(new ListAndSum(array[i]));
}else if(array[i] == 0){ // for already 0's in array, put them directly into the result
List<Integer> listItem = new ArrayList<Integer>();
listItem.add(array[i]);
result.add(new HashSet<Integer>(listItem));
}
}
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.
result.add(satisFiedSet);
}
}
}
}
}
System.out.println("Results: ");
for(Set<Integer> s: result){
System.out.println(s);
}
}
}
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.
/* 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
{
// your code goes here
int a[] ={8,3,5,1,-4,-8};
printSubsetOfSumZero(a);
}
}
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();
}
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);
}
Console.ReadLine();
}
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))
ans.Add(new Result(input[i], input[j], input[k]));
}
}
}
foreach (Result item in ans)
{
Console.WriteLine(item.x+" "+item.y+" "+item.z);
}
Console.ReadLine();
}
}
How about this?
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]);
}
}
}
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;
}
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) {
vector<int> mask(v.size(), 0);
mask.front() = 1;
while (TryInc(mask)) {
// 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)
if (mask[i])
printf("%d ", v[i]);
printf("\n");
}
}
}
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.
How about this solution? It finds all the subset :)
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];
sublist.add(list[i]);
positions.add(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) {
solution.add(sublist.toString());
}
}
public static void main(String[] args) {
long[] list = new long []{8, 3, 5, 1, -4, -8, 0};
sumsZero(list);
}
}
How about this solution? It finds all the subset :)
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];
sublist.add(list[i]);
positions.add(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) {
solution.add(sublist.toString());
}
}
public static void main(String[] args) {
long[] list = new long []{8, 3, 5, 1, -4, -8, 0};
sumsZero(list);
}
}}} }
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--;
}
}
}
{{
#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--;
}
}
}
}}
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)
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);
}
}
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);
}
}
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);
}
}
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>>();
//add result into temp;
for(List<Integer> list : result)
temp.add(new ArrayList<Integer>(list));
//add new element to every list
for(List<Integer> list : temp)
list.add(nums[i]);
//add single list;
List<Integer> single = new ArrayList<Integer>();
single.add(nums[i]);
temp.add(single);
//assgin to result
result.addAll(temp);
}
//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);
}
}
}
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;
}
}
}
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;
}
}
}
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);
}
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);
}
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)
#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;
}
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:
- autoboli January 09, 2015private 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 } }