# Subset Sum Problem 1

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.

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