# 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 {
int i, r = 0;
sos o = new sos();
System.out.println(" enter the number of elements of set: ");
System.out.print("\n enter the elements: ");
for (i = 0; i < n; i++) {
r = r + o.w[i];
}

System.out.print("\n enter the sum to be computed: ");
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...

*/
```

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