Given a set of positive integers and a value sum,the task is to find if there is a subset with sum equal to the given value.
Example-
Given set of numbers- {3,34,4,12,5,2}
Sum=9.
The output will be ‘True’ because 4+5=9.
Algorithm-
The problem can be divided into two sub-problems-
1.By including the last element.
2.By excluding the last element.
Recursive Solution-
[cpp]
subsum(set, n, sum) = subsum(set, n-1, sum) //excluding the last element
|| subsum(arr, n-1, sum-set[n-1]) //including the last element
Base Cases:
subsum(set, n, sum) = false, if sum > 0 and n == 0
subsum(set, n, sum) = true, if sum == 0
[/cpp]
Code-
The above algorithm has exponential time complexity which can be converted to code having polynomial complexity using dynamic programming that is storing the intermediate results.
[cpp]
// Returns true if there is a subset of set[] with sum equal to given sum
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[sum+1][n+1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[0][i] = true;
// If sum is not 0 and set is empty, then answer is false
for (int i = 1; i <= sum; i++)
subset[i][0] = false;
// Fill the subset table in bottom up manner
for (int i = 1; i <= sum; i++)
{
for (int j = 1; j <= n; j++)
{
subset[i][j] = subset[i][j-1];
if (i >= set[j-1])
subset[i][j] = subset[i][j] || subset[i – set[j-1]][j-1];
}
}
return subset[sum][n];
}
[/cpp]
