fork download
copy 
  1. #include <stdio.h>
  2.  
  3. // Returns true if there is a subset of set[] with sun equal to given sum
  4. bool isSubsetSum(int set[], int n, int sum)
  5. {
  6.    // Base Cases
  7.    if (sum == 0)
  8.      return true;
  9.    if(sum<0)
  10.    return 0;
  11.    if (n == 0 && sum != 0)
  12.      return false;
  13.  
  14.    /* else, check if sum can be obtained by any of the following
  15.       (a) including the last element
  16.       (b) excluding the last element   */
  17.    return isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1]);
  18. }
  19.  
  20. // Driver program to test above function
  21. int main()
  22. {
  23.   int set[] = {3, 34, 4, 12, 15, 2};
  24.   int sum = 8;
  25.   int n = sizeof(set)/sizeof(set[0]);
  26.   if (isSubsetSum(set, n, sum) == true)
  27.      printf("Found a subset with given sum");
  28.   else
  29.      printf("No subset with given sum");
  30.   return 0;
  31. }
Success #stdin #stdout 0s 3296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
No subset with given sum
https://ideone.com/Gr9pEv
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!