Subset Sum Problem

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;
}
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
CHP Adblock Detector Plugin | Codehelppro