Code not working

#1

The problem is named: Subset Sum easy.
my Solution:

Approach: to calculate all the subset sums by traversing through the array, and which is easy, given the small value of N in the problem. At each step we have 2 options, either we take the Ith element or move ahead without taking it. in the right most corner of the recursive tree, there will be a case where we have not taken any element from the array and thus the value will be equal to the value that we are passing, i.e 0. So, this case will always be present. We want atleast one more case with sum of subset after traversing the array=0. We have used a counter for checking this.

Please help in why the code is not working.

#2

hello @anshufirefox

check now

also note u have t test cases so u need to read t and run ur logic for t time

also dont forget to initilaise c with 0 in every case

#4

Got it, Thank you :slight_smile:

#5

Could you please see why is it not working completely??

Problem: Given an array of number and a target sum, count number of subsets as such that the sum of elements of the subset is equal to the given sum

Solution: https://ide.codingblocks.com/s/479409

#6

It works when I use + instead of doing or in my recurrence relation. But, the counter method should give the answer as well. Why doesn’t it?

#7

or and addition are not the same thing.

in case of or the result will be either 1 0r 0 and hence in dp array u will be sotring 0 or 1 which is clearly wrong

#8

I know the difference. One approach to solve this problem is to use the plus, which is working.
The other method which I am talking about is to treat the problem just like the subset sum problem.

int Check(int arr[], int sum, int N)
{
if(N==0 && sum ==0)
{
++c;
return 1;
}
if(N==0 && sum!=0 ) return 0;
if(dp[N][sum]!=-1) return dp[N][sum];
if(arr[N-1]<=sum)
return dp[N][sum]= (Check(arr, sum-arr[N-1], N-1) or Check(arr, sum, N-1));
else
return dp[N][sum] = Check(arr, sum, N-1);

}

Here, we just try to traverse the array from the end to the front taking two potions at every level i.e including the element or not including the element if the element is smaller than the sum and not including the element if the element is greater than the sum. It’s just like subset sum. The only difference that i wanted to include was to use a counter for when the base case is reached and the sum=0. It’s just basically counting the number of times when N==0 and sum==0 happen.

#9

options* instead of potions

#10

bro u need to understand that when u apply dp, then some values get saved in dp table and it get used for later calls.

now what u are storing in dp table ? u are only storing 0 or 1 becuase of which
a) the number of function call will reduce
b) the dp entries will have wrong results. they are suppose to hold count but all they are holding is 0 or 1.

pls revise ur dp fundamentals

#11

I am thinking on the line of though that you pointed out. Maybe it will click if I keep thinking. However, as per how I designed the code, my purpose was not to use the dp table entries as the result. I know the dp matrix is full of 1s and 0s. I understand what memoization is. This is why I am just letting the code run and printing the counter at last. Sorry, if this is irritating.

#12

the issue is due to dp only and to understand issue u need to understand so pls
…

…

#13

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.