I somehow got it correct by brute force.how can i apply dp for this problem

#1
#2

@neha_153 hi ,waise ye qstn recursion se submit hoga ,we can also solve this problem in bottom-up manner. In the bottom-up approach, we solve smaller sub-problems first, then solve larger sub-problems from them. The following bottom-up approach computes , for each and , which is true if subset with sum j can be found using items up to first i items. It uses value of smaller values i and j already computed. It has the same asymptotic run-time as Memoization but no recursion overhead.
Here is pseudo code for that:
bool subsetSum(int *arr, int n, int target) {
bool *dp = new bool[n+1];
for(int i=0;i<=n;i++) {
dp[i] = new bool[target+1];
}
dp[0][0] = true; // If sum is zero and no element is taken ans is true
for(int i=1;i<=n;i++) { // If sum is zero ans is always true
dp[i][0] = true;
}
for(int i=1;i<=target;i++) { // If no element is chosen and sum is not zero ans is false
dp[0][i] = false;
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=target;j++) {
if(j<arr[i-1]) {
dp[i][j] = dp[i-1][j];
}
if(j>=arr[i-1]) {
dp[i][j] = dp[i-1][j] or dp[i-1][j-arr[i-1]];
}
}
}
return dp[n][target];

}

Target is 0 in our case.Hope you get it :slight_smile:

#3

why did u use or in the second case

#4

@neha_153 hi ,basically we check if sum can be obtained by any of the following
(a) including the last element
(b) excluding the last element
Agar dono me se koi bhi true horha hai mtlb ki woh true ayegi dp.We have use || operator like this:
return isSubsetSum(set, n-1, sum) ||
isSubsetSum(set, n-1, sum-set[n-1]);

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.