Question

(In C) Given a list of numbers, find all the subsets of that list that sum up to a given number? Ex: generate all subsets of {2, 4, 3, 1, 6, 5, 9} that sum up to 7. Output should be: {2, 4, 1}, {3, 4}, {5, 2}, {2, 1, 4}, {6, 1}

Answer 1

// A recursive solution for subset sum problem
#include <stdio.h>

// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
// Base Cases
if (sum == 0)
   return true;
if (n == 0 && sum != 0)
   return false;

// If last element is greater than sum, then ignore it
if (set[n-1] > sum)
   return isSubsetSum(set, n-1, sum);

/* else, check if sum can be obtained by any of the following
   (a) including the last element
   (b) excluding the last element */
return isSubsetSum(set, n-1, sum) ||
                       isSubsetSum(set, n-1, sum-set[n-1]);
}

// Driver program to test above function
int main()
{
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = sizeof(set)/sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
   printf("Found a subset with given sum");
else
   printf("No subset with given sum");
return 0;
}