I did using recursion but want to do it with dp

#1

Other version of same problem that is subset sum for non zero number i did using dp and created matrix.But how will i create matrix for this? coz 0 will be first coloumn itself with all ones

#2

In that i created rows as the numbers given and coloumns as number from 0 to target

#3

But here itself is 0

#4

hello @pranjalarora98

make dp of this size -> dp[n+1][max_sum_possible_from_array]

and then after running ur code check dp[n][0] for answer

#5

hey one doubt then
dp[n+1][max_sum_possible_from_array]
max_sum_possible_from_array?
What will it be

#6

summation of all positive number in the given array

#7

max sum possible will i have to calculate then?first

#8

yes. . . . . . . . .

#9

Just 1 more doubt can u plz tell intution with how u came up with this logic?

#10

recursion bro
pick ith element or ignore ith element then check whether generated subset is zero or not and decide answer accordingly

#11

when i was doing for target sum==k.Then i had initialised 0th row first element as 1 and then all 0
And then wh0le coloumn of 0th index as 1

#12

here fill 1st row manually(index 1) .

i,e
dp[1][a[0]=1;
and rest all as 0.
and then start fiilling ur dp array from i=2

#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.