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

Leave a Reply

Your email address will not be published. Required fields are marked *