//SUM OF SUBSETS PROBLEM
import java.io.*;
import java.util.*;
public class SumOfSubsets
{
static int [] w;
static int [] x;
public static BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
public static void SumOfSubsets(int s, int k, int r, int m)
{
int i;
x[k]=1;
if((s+w[k])==m)
{
System.out.print("{");
for(i=1;i<=k;i++) System.out.print(x[i]+" ");
System.out.print("}\t");
}
else if((s+w[k]+w[k+1])<=m)
{
SumOfSubsets(s+w[k],k+1,r-w[k],m);
}
if(((s+r-w[k])>=m)&&((s+w[k+1])<=m))
{
x[k]=0;
SumOfSubsets(s,k+1,r-w[k],m);
}
}
public static void main(String[] args) throws IOException
{
int i,j,temp,ord,max,sum=0;
System.out.println("\t\t\t\tSUM OF SUBSETS");
System.out.print("\n\nEnter the order of the set: ");
ord = Integer.parseInt(br.readLine());
w = new int[ord+1];
x = new int[ord+1];
System.out.println("\n\nEnter the elements of the set:");
for(i=1;i<=ord;i++)
{
System.out.print("Element #"+i+": ");
w[i] = Integer.parseInt(br.readLine());
sum+=w[i];
}
System.out.println("\nEnter the sum to be made: ");
max = Integer.parseInt(br.readLine());
Arrays.sort(w, 1, w.length);
if((max<w[1])||(sum < max))
System.out.print("Sorry, Subsets can't be formed.");
else
{
System.out.print("\nGiven set: \n{");
for(i=1;i<=ord;System.out.print(w[i]+" "),i++);
System.out.print("}");
System.out.println("\n\nSubsets formed with sum as "+max+": ");
SumOfSubsets.SumOfSubsets(0,1,sum,max);
}
}
}