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.
https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
Recursion
class Solution {
static boolean isSumK(int[] nums, int curin, int curSum) {
if(curSum==0) {
return true;
}
if(curin<0) {
return false;
}
return isSumK(nums, curin-1, curSum-nums[curin])
|| isSumK(nums, curin-1, curSum);
}
With Memorization
class Solution{
static int issum(int arr[], int indx, int sum, int dp[][]) {
if(sum==0)
return 1;
if(indx<0)
return 0;
if(dp[indx][sum]!=-1)
return dp[indx][sum];
int pick = 0;
if(sum>=arr[indx])
pick = issum(arr, indx-1, sum-arr[indx],dp);
int notpick = issum(arr, indx-1, sum,dp);
if(pick==1 || notpick==1)
return dp[indx][sum] = 1;
return dp[indx][sum] = 0;
}
