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