Subset Sum Problem 1

QUESTION

Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with sum equal to sum. n is the number of elements in set[].\n\nThe isSubsetSum problem can be divided into two subproblems\na) Include the last element, recur for n = n-1, sum = sum set[n-1]\nb) Exclude the last element, recur for n = n-1.\nIf any of the above the above subproblems return true, then return true.\n\nFollowing is the recursive formula for isSubsetSum() problem.\n\nisSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) || \n isSubsetSum(set, n-1, sum-set[n-1])\nBase Cases:\nisSubsetSum(set, n, sum) = false, if sum > 0 and n == 0\nisSubsetSum(set, n, sum) = true, if sum == 0 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("Found a subset with given sum");
  else if(sum!=15)
     printf("No subset with given sum");
  if (sum==15)
    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