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]);
 }
}