QUESTION

The Sum of Subset problem can be gi+E13ve 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 ).\n\nFor 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}.

ANSWER

#include<stdio.h>
#include<stdlib.h>
void sumOfSub(int,int,int);
static int m=0;
int*w;
int*x;
int main()
{ int i=0,sum=0,n=0;
 scanf("%d",&n);
 w=(int*)malloc(sizeof(int)*n+1);
 x=(int*)malloc(sizeof(int)*n+1);
 for(i=1;i<=n;i++)
 {
  scanf("%d",&w[i]);
  sum+=w[i];
  x[i]=0;
 }
 scanf("%d",&m);
 if(sum<m)
 {
 exit(1);
 }
 sumOfSub(0,1,sum);
return 0;
}

void sumOfSub(int s,int k,int r)
{ 
  int i=0;
 x[k]=1;
 if(s+w[k]==m)
 { 
  for(i=1;i<=k;i++)
  printf(" %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]);
 }
}