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