QUESTION
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum. Let the sum be 9.
ANSWER
#include <stdio.h>
#include <stdbool.h>
bool isSubsetSum(int set[], int n, int sum)
{
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;
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[100],i,n;
int sum = 9;
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d",&set[i]);
if (isSubsetSum(set, n, sum) == true)
printf("Found a subset with given sum");
else
printf("No subset with given sum");
return 0;
}