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.

Powered By
100% Free SEO Tools - Tool Kits PRO