Thursday, April 14, 2011

Sum Of Subsets


import java.util.*;
import java.io.*;
class Demo
{
int m;
int w[],n,x[];
public static void main(String arg[])
{
Scanner in=new Scanner(System.in);
int i,r=0;
System.out.println("Enter Enter the no. elements of set");
n=in.nextInt();
System.out.println("Enter the elements");
for(i=0;i<n;i++)
{
w[i]=in.nextInt();
r=r+w[i];
}
System.out.println("Enter the sum to be computed");
m=in.nextInt();
System.out.println("Subsets whose sum is "+m+"are as follows");
Sum0fSub(0,0,r);
}
void Sum0fSub(int s,int k,int r)
{
int i;
x[k]=1;
if(s+w[k]==m)
{
for(i=0;i<=k;i++)
System.out.println(x[i]);
System.out.println();
System.out.println("Elements of set are");
for(i=0;i<=k;i++)
if(x[i]==1)
System.out.println(w[i]);
System.out.println();
}
else if((s+w[k]+w[k+1]<=m))
Sum0fsub(s+w[k],k+1,r-w[k]);
if((s+r-w[k]>=m)&&(s+w[k+1]<=m))
{
x[k]=0;
Sum0fSub(s,k+1,r-w[k]);
}
}
}

     OUTPUT


Enter the no. elements of set
6
Enter the eements
5
10
12
13
15
18
Enter the sum to be computed
30

Subsets whose sum is 30are as follows
1  1  0  0  1

Elements of set are
5  10  15
1  0  1  1

Elements of set are
5  12  13
0  0  1  0  0  1

Elements of set are
12  18