QUESTION

Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with sum equal to sum. n is the number of elements in set[].\n\nThe isSubsetSum problem can be divided into two subproblems\na) Include the last element, recur for n = n-1, sum = sum set[n-1]\nb) Exclude the last element, recur for n = n-1.\nIf any of the above the above subproblems return true, then return true.\n\nFollowing is the recursive formula for isSubsetSum() problem.\n\nisSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) || \n isSubsetSum(set, n-1, sum-set[n-1])\nBase Cases:\nisSubsetSum(set, n, sum) = false, if sum > 0 and n == 0\nisSubsetSum(set, n, sum) = true, if sum == 0 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("Found a subset with given sum");
  else if(sum!=15)
     printf("No subset with given sum");
  if (sum==15)
    printf("No subset with given sum");
  return 0;
}