Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Example:
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
There is a subset (4, 5) with sum 9.
Subset Sum Problem! - InterviewBit
for(i = 0; i <= n; i++)
{
for(w = 0; w <= W; w++)
{
//Base Conditions
//if weight of current item is less than or equal to current Knapsack capacity
if (wt[i - 1] <= w)
dp[i][w] = max(val[i - 1] +
dp[i - 1][w - wt[i - 1]],
dp[i - 1][w]);
else
dp[i][w] = dp[i - 1][w];
}
}
return dp[n][W];
max function from 0/1 Knapsack is converted into ||. Also since no val[] array is given to us hence it is omitted.
for(int i=0;i<=n;i++)
{
for(int j=0;j<=sum;j++)
{
//Base Conditions
if(i==0&&j!=0)
dp[i][j] = false;
else if(j==0)
dp[i][j] = true;
//If the current element of the set is less than or equal to the current sum
else if(nums[i-1]<=j)
//including || excluding the current element
dp[i][j] = dp[i-1][j-nums[i-1]] || dp[i-1][j];
else
dp[i][j] = dp[i-1][j]; //excluding the current element
}
}
return dp[n][sum];