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