Implementing Sum of Subset by Backtracking in Java

Subset sum problem is to find subset of elements that are selected from a given set whose sum adds up to a given number K.

import java.io.*;
import java.util.*;
import java.lang.*;


class sos {
    int m;
    int w[];
    int x[];
    public sos() {
        w = new int[40];
        x = new int[40];
    }

    public void sos1(int s, int k, int r) {
        int i;
        x[k] = 1;
        if (s + w[k] == m) {
            for (i = 0; i <= k; i++)
                System.out.print(x[i] + "\t");
            System.out.println();
            System.out.print(" elements of set are \n");
            for (i = 0; i <= k; i++)

                if (x[i] == 1)

                    System.out.print(w[i] + "\t");

            System.out.println();

        } else if ((s + w[k] + w[k + 1]) <= m)
            sos1(s + w[k], k + 1, r - w[k]);
        if ((s + r - w[k] >= m) && (s + w[k + 1] <= m)) {
            x[k] = 0;
            sos1(s, k + 1, r - w[k]);
        }
    }
}




class sosdemo {
    public static void main(String args[]) throws IOException {
        BufferedReader Bobj = new BufferedReader(new InputStreamReader(System.in));
        int i, r = 0;
        sos o = new sos();
        System.out.println(" enter the number of elements of set: ");
        int n = Integer.parseInt(Bobj.readLine());
        System.out.print("\n enter the elements: ");
        for (i = 0; i < n; i++) {
            o.w[i] = Integer.parseInt(Bobj.readLine());
            r = r + o.w[i];
        }

        System.out.print("\n enter the sum to be computed: ");
        o.m = Integer.parseInt(Bobj.readLine());
        System.out.print(" \n subset whose sum is " + o.m + " are as follows: ");
        o.sos1(0, 0, r);
    }
}




/*   
  output
    
enter the number of elements of set: 4
enter the elements: 
11 13 24 7
enter the sum to be computed: 31 
subset whose sum is 31 are as follows:
 0  0  1  1	
elements of set are 
24	7	
Process Exit...

*/

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.