22. SUM OF SUBSETS PROBLEM

Code:

import java.util.*;

class SumOfSubsets

{

            static int w[],x[],i,j,s=0,k=1,r=0,m,n;

            void read()

            {

                        Scanner s=new Scanner(System.in);

                        System.out.println("Plaese enter the number of values");

                        n=s.nextInt();

                        w=new int[n+1];

                        x=new int[n+1];

                        System.out.println("Plaese enter the corresponding weights");

                        for(i=1;i<=n;i++)

                        {

                                    System.out.println("Please enter the weight");

                                    w[i]=s.nextInt();

                                    r+=w[i];

                                    x[i]=0;

                        }

                        System.out.println("Please enter the total sum");

                        m=s.nextInt();

            }

            void sumOfSubset(int s,int k, int r)

            {

                        if(s+w[k]==m)

                                    {

                                    x[i]=1;

                                    System.out.println("Possible Solutions are");

                                    for(i=1;i<=n;i++)

                                                System.out.print(" "+x[i]);

                                    System.out.println();

                                    }

                        else if(s+w[k]+w[k+1]<=m)

                                    {

                                                x[k]=1;

                                                sumOfSubset(s+w[k],k+1,r-w[k]);

                                    }

                        if((s+r-w[k]>=m)&&(s+w[k+1]<=m))

                                    {

                                                x[k]=0;

                                                sumOfSubset(s,k+1,r-w[k]);

                                    }

            }

            public static void main(String args[])

            {

                        SumOfSubsets ss=new SumOfSubsets();

                        ss.read();

                        ss.sumOfSubset(s,k,r);

            }

}

Output:

Please enter the number of values

4

Please enter the corresponding weights

Please enter the weight

7

Please enter the weight

11

Please enter the weight

13

Please enter the weight

24

Please enter the total sum

31

Possible Solutions are

 1 1 1 0

Possible Solutions are

 1 0 0 1

Need the code??

Download Link= https://www.dropbox.com/s/az8gt9cfjlcbsfh/8%20Sum%20of%20Subsets.docx