Subset Sum Problem


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.


#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;
  for (i=1;i<=n;i++)
  if (isSubsetSum(set, n, sum) == true)
     printf("Found a subset with given sum");
     printf("No subset with given sum");
  return 0;
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.