Subset Problem

8. Find a subset of a given set S = {s1,s2,…..,sn} of n positive integers whose sum is equal to a given positive integer d. For example, if S= {1, 2, 5, 6, 8} and d = 9 there are two solutions {1,2,6} and {1,8}.A suitable message is to be displayed if the given problem instance doesn’t have a solution.

#include<stdio.h>
#include<stdlib.h>

void subset(int, int, int);

int w[10],n,d,i,cs,r,x[10],sum=0,k,c;

void main()
{
  printf("\n\n************SUBSET PROBLEM*********\n\n");
  printf("Enter the number of elements:");
  scanf("%d",&n);
  printf("\n\n Enter the elements in increasing order:");
  for(i=0;i<n;i++)
      scanf("%d",&w[i]);
  printf("\n\nEnter the value of d:");
  scanf("%d",&d);
  for(i=0;i<n;i++)
        sum=sum+w[i];
  printf("\n\nSUM=%d",sum);
  if(sum<d||w[0]>d)
  {
     printf("\n\n Subset is not posssible!");
     printf("\n\n*************** *********** **************\n\n");
     exit(0);
  }
  subset(0,0,sum);
  if(c==0)
      printf("\n\nSubset is not possible !");
  printf("\n\n********* ************ ************\n\n");
}
void subset(int cs, int k, int r)
 {
      x[k]=1;
      if(cs+w[k]==d)
       {
         printf("\n\n Solutiion %d is={",++c);
         for(i=0;i<=k;i++)
                if(x[i]==1)
                 {
                     printf("%d",w[i]);
                 }
                 printf("\b}");
       }
       else if((cs+w[k]+w[k+1])<=d)
              subset(cs+w[k],k+1,r-w[k]);
       if((cs+r-w[k])>=d&&(cs+w[k+1])<=d)
        {
           x[k]=0;
           subset(cs,k+1,r-w[k]);
        }
 }



OUTPUT:

Enter the number of elements:5

Enter the elements in increasing order:  1  2  3  6  8

Enter the value of d:9