Question

Create a simple main() that solves the subset sum problem for any vector of ints. Here is an example of the set-up and output. You would fill in the actual code that makes it happen. int main() { int TARGET

Answer 1

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[].

The isSubsetSum problem can be divided into two subproblems

…a) Include the last element, recur for n = n-1, sum = sum – set[n-1]

…b) Exclude the last element, recur for n = n-1.

If any of the above the above subproblems return true, then return true.

Step-by-step explanation:

Using C++

// 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)

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;

}

Output:

Found a subset with given sum