The Subset Sum

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]);
 }
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro