CareerCup

#include<stdio.h>
#include<conio.h>
int min(int);
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; 
    }

This would give all the possible outputs

set1="5,3,1,8, -8,-4"
def getSum(set2):
    sum=0
    for i in set2.split(','):
        try:
            sum+=int(i.strip())
        except:
            continue
    return sum
def func1(set1,set2,i):
    if i < len(set1.split(',')):
        func1(set1,set2,i+1)
        set2+="%s,"%set1.split(',')[i]
        func1(set1,set2,i+1)
        if getSum(set2)==0:
            print set2
        
func1(set1,"",0)

outputs=>
8, -8,
3,1,-4,
3,1,8, -8,-4,
5,3, -8,

we can use hash map for this problem with o(N)

One of way to achieve this via brutal force is to generate the POWER set of the given set. Then check each of the POWER set if the sum of all the elements is equal to zero.

Please refer here for generating POWER set (recursive and non-recursive implementations):
cpluspluslearning-petert.blogspot.co.uk/2014/04/dynamic-programming-generate-power-set.html

The major problem here is the space complexity. Assume the given set has the size of N, then the POWER set has the size of 2^N (refer to cpluspluslearning-petert.blogspot.co.uk/2014/04/dynamic-programming-generate-power-set.html). The space complexity is O(2^N). According to Apurohit.in's description N could reach 100. This is a challenge to generate the POWER set and keep in memory. Need more investigation......

Continue with my last comments. I was thinking of if there are any heuristic rules to help the searching.

My method is to sort the given set into 3 different portions: the negative sets, Sn, zero elements sets, So, and the positive element sets, Sp. We can ignore the zero elements set for now because they can either appear or not appear in the solution sub-set. Therefore any solution sub-set have to have negative and positive elements. The idea is to generate sub-sets from the Sp ( with a known NegativeSum) first and then to find a sub-set in Sp, whose sum is equal to the absolute value of NegativeSum.

The heuristic rules:
- Sn or Sp is empty, no need to search
- So is not empty
* Found solutions from Sn and Sp, then the number of solution sub-set expand time of
2^SizeOf(So)
* Not found, then the number of solution sub-sets are 2^SizeOf(So) -1. The solution
sub-sets are made of all zeros.
- If the sum of the current sub-set of Sp is more than the absolute value of NegativeSum,
then stop the search in the Sp because taking any extra element in from Sp will simply
cause the sum of the positive sub-set higher.

The details please refer to: cpluspluslearning-petert.blogspot.co.uk/2015/02/dynamic-programming-list-all-sub-sets.html

/* 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 main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		int[] arr = {5,3,1,8,-8,-4};
		for(int i=0;i<arr.length;i++){
			printAllZeroSets(arr,i,0,0);
		}
		
	}
	
	public static void printAllZeroSets(int[] arr, int start, int currSum, int total){
		if(start>arr.length-1){
			return;
		}
		
		int thisValue = arr[start];
		if(currSum + thisValue == total){
			System.out.println(thisValue + "," +  currSum);
			return;
		}
		for(int i=start+1; i<arr.length; i++){
			if(currSum + thisValue + arr[i] == total){
				System.out.println(arr[i] + "," + thisValue + "," +  currSum);
			}
		}
		printAllZeroSets(arr, start+1, currSum+thisValue, total);
	}
}