Programming Geek
Rated 4.1/5 based on 446 reviews

### Sum of Subset

The Sum of Subset problem can be give as: Suppose we are given n distinct numbers and we desire to find all combinations of these numbers whose sums are a given number ( m ).

For example, if n=4 i.e there are four numbers as: 1, 2, 3, 4, 5 and m=5 the all possible subsets are as : {1,4},{2,3},{5}

The following programs finds all subsets using backtracking:

JAVA implementation:

```import java.util.Scanner;

/**
*
* @author VIK VIKKU VIKASHVVERMA VIKASH
*
* @Website: http://vikash-thiswillgoaway.blogspot.com
*
*/
public class SumOfSubsets {

int[] w;
int[] x;
int sum;

public void process() {
getData();
}

private void getData() {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number of elements:");
int n = sc.nextInt();
w = new int[n + 1];
x = new int[n + 1];
int total = 0;
System.out.println("Enter " + n + " Elements :");
for (int i = 1; i < n + 1; i++) {
w[i] = sc.nextInt();
total += w[i];
}
System.out.println("Enter the sum to be obtained: ");
sum = sc.nextInt();
if (total < sum) {
System.out.println("Not possible to obtain the subset!!!");
System.exit(1);
}
subset(0, 1, total);
}

private void subset(int s, int k, int r) {
int i = 0;
x[k] = 1;
if (s + w[k] == sum) {
System.out.println();
for (i = 1; i <= k; i++) {
System.out.print("\t" + x[i]);
}
} else if ((s + w[k] + w[k + 1]) <= sum) {
subset(s + w[k], k + 1, r - w[k]);
}
if ((s + r - w[k]) >= sum && (s + w[k + 1]) <= sum) {
x[k] = 0;
subset(s, k + 1, r - w[k]);
}
}

public static void main(String[] args) {
new SumOfSubsets().process();
}
}

```

C Implementation:

```#include < stdio.h >

void sumOfSub(int,int,int);
static int m=0;
int*w;
int*x;
void main()
{ int i=0,sum=0,n=0;
printf("Enter size of array: ");
scanf("%d",&n);
w=(int*)malloc(sizeof(int)*n+1);
x=(int*)malloc(sizeof(int)*n+1);
printf("Enter %d elements: ",n);
for(i=1;i < =n;i++)
{
scanf("%d",&w[i]);
sum+=w[i];
x[i]=0;
}
printf("Enter the sum to be obtained: ");
scanf("%d",&m);
if(sum < m)
{
printf("Not possible to obtain any subset !!! ");
exit(1);
}
printf("Possible Subsets are( 0 indicates exclusion and 1 indicates inclusion) : ");
sumOfSub(0,1,sum);
}

void sumOfSub(int s,int k,int r)
{ int i=0;
x[k]=1;
if(s+w[k]==m)
{ printf("\n");
for(i=1;i < =k;i++)
printf("\t%d",x[i]);
}
else if((s+w[k]+w[k+1]) < =m)
{
sumOfSub(s+w[k],k+1,r-w[k]);
}
if((s+r-w[k]) > =m && (s+w[k+1]) < =m)
{
x[k]=0;
sumOfSub(s,k+1,r-w[k]);
}
}
```