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

Answer:

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.

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)

{

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

}

Output:

Found a subset with given sum