Question

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3, ..., an} and positive integer W, is there a subset of S whose elements sum to W? Design a dynamic program to solve the problem. (Hint: uses a 2-dimensional Boolean array X, with n rows and W+1 columns, i.e., X[i, j] = 1,1 <= i <= n, 0 <= j <= W, if and only if there is a subset of {a1, a2, ..., ai} whose elements sum to j). Justify your answer

PLEASE HELP

Answer 1

The function returns true if a subset exists and false if subset doesn't exist

bool isSubsetSum(int set[], int n, int sum)
{
// The value of subset[i][j] will be true if there is a
// subset of set[0..j-1] with sum equal to i
bool subset[n+1][sum+1];

// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[i][0] = true;

// If sum is not 0 and set is empty, then answer is false
for (int i = 1; i <= sum; i++)
subset[0][i] = false;

// Fill the subset table in botton up manner
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= sum; j++)
{
if(j<set[i-1])
subset[i][j] = subset[i-1][j];
if (j >= set[i-1])
subset[i][j] = subset[i-1][j] || subset[i - 1][j-set[i-1]];
}
}
return subset[n][sum];
}