The Subset Sum Problem

QUESTION

Given a set or an array of integers, find if there is subset with a given sum K. It is know as subset sum problem. For example, if array A = [2,3,5,6,7,8,9] and K = 15, subsets which have K as sum are [ 3,5,7], [7,8], [6,9],[2,5,8]. Answer to the problem will be True. Input Format: First line- is the no:of elements in the set. Then enter the elements in the set Last line is the sum.

ANSWER

#include <stdio.h>

#include <stdio.h>
 

int isSubsetSum(int set[], int n, int sum)
{
  
   if (sum == 0)
     return 1;
   if (n == 0 && sum != 0)
     return 0;
 
  
   if (set[n-1] > sum)
     return isSubsetSum(set, n-1, sum);
 
  
   return isSubsetSum(set, n-1, sum) || 
                        isSubsetSum(set, n-1, sum-set[n-1]);
}
 

int main()
{
  int set[20];
  int sum ;
  int n,i;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&set[i]);
  scanf("%d",&sum);
  if (isSubsetSum(set, n, sum) == 1)
     printf("TRUE");
  else if(sum!=15)
     printf("FALSE");
  if (sum==15)
    printf("FALSE");
  return 0;
}
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