DP 17. Counts Subsets with Sum K | Dp on Subsequences

[@takeUforward]

I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you. The test case {0,0,1} has been explained in the DP 18 video.. Keeping a like target of 500 ❤✌🏼

[@kartikaymahajan9591]

Leetcode 473. Matchsticks to Square. I think this can be added to your playlist.it a variation of partition equal subset sum. what u say striver

[@harshdasila6680]

@@kartikaymahajan9591 does this count subset with sum problem available on leetcode?

[@vishalkumarshaw9208]

You deserve a million like striver... ❤️

[@amitranjan6998]

@take U forward : I am loving your video and learning alot , I have one small confusion ,inside second for loop why you started sum=0 -> target in tabulation format ,why not start with sum=1 -> target;

[@alltechpoint8508]

done target

[@tc2games176]

This is so nice that even if you have covered the concept(specific pattern), you are repeating it for the other variants of the question, so that it remains on the brain, it takes a lot of effort to do that, Thank you so much for all you do.

[@avneeshgoyal4554]

map can be used for storing for negative values. where key is {index,sum}

[@rishabhgupta9846]

can you share solution using map ,I'm getting wrong answer

[@thomasshelby6780]

since when map is defined like that ,it must be map mp;

[@drago3393]

For anyone facing a problem in the test case - {0, 0, 1} Just sort the given nums array in descending order. It will make the array {1, 0, 0} and will consider all the subsets containing zeros.

[@lakeshkumar1252]

thanks bhai

[@MadhavGupta-fi2tu]

or else u can count number of zeros and return pow(2,n)

[@vaibhavjaiswal7811]

Wow! This really blew my mind. So simple. Thanks

[@yashhokte1020]

Bro intuition behind it? Why we need to sort it in descending order?

[@karthik53r35]

@@yashhokte1020 doing that will make all zero's behind thus considering both not pick and pick counts while adding

[@anuragpandey8165]

OMG you are magical, I was able to write recursive soln on my own, then memoized it on my own, tabulated as well as space optimized on my own before looking the video! I am making progress. All because of you.

[@parthsalat]

*Code timestamps* Recursion: 15:00 Memoization: 20:50 Tabulation: 33:50 *Complexities timestamps* Recursion: 15:40 Memoization: 21:08

[@DeepthiAcharya-xk8uz]

lecture 16 ka negative testcase ko handle kaise kare, uska bhi timestamp bataado na bhayya

[@2xReturns-FOOTBALL]

striver's love for lec-7 is unreal

[@INTO2509]

same dp bro

[@ranjeet_sohanpal]

Thala for a reason

[@subhajitdey135]

I think the condition "if (target==0) return 1 " at 13:15 will not be totally valid if we have numbers like 0 in the array. So it will possibly be best if we check at the end for every possible subsequence. And Like if we don't have any number like 0 in the array, then this condition would be totally valid.

[@TheK_Fam]

you could just add that extra condition if i == 1: ways = 0 if remaining == 0 and arr[0] == 0: # If the only item is 0 and remaining sum is 0, there are 2 ways (include or exclude the 0) ways = 2 elif remaining == 0 or remaining == arr[0]: # If remaining sum is 0 or equals the only item, there's 1 way ways = 1 return ways

[@TheK_Fam]

dp = [[-1 for _ in range(k + 1)] for _ in range(n + 1)]

[@ShubhamKumar-re4zv]

Yes you are correct

[@divy04]

or we can store the non zero elements in some other array, pass it in the function, count the number of zero elements, and multiply the answer by 2^count

[@after_dark_777]

@@divy04 your trick is failing in the 48th test case

[@AnushkaGupta-x6w]

All those asking why 2nd loop in tabulation starts from sum=0 and not 1 because because , guys we have to tell totals subsets with sum= target so if we have had target=0 then you would have already stored the answer of dp[n-1][0]=1 Which is correct if arr did not have any integer as 0 , in case 0 are there then this subset with 0 is also a valid answer hence we need to count it as well eg arr=[0,2 3] target=0 so total answer is 2 not 1, so we recalculate the value of dp[i][0] to ensure if we are getting any more subsets with sum=0 apart from the empty subset. I hope you understood my point

[@pranaykumar9186]

then it should be applied to all previous questions also , there second loop should also start from 0 instead of 1.

[@kunalgupta343]

Try with [0,1,0] with target 0.

[@AnushkaGupta-x6w]

@@kunalgupta343 4 i guess, All subsets possible are- Null 0 a first index 0,0 0 at last index

[@biswajitadhikary_0807]

@@AnushkaGupta-x6w it is 3 0 0 0 0

[@clashtm8210]

I can't comprehend that, can you rephrase what you have written?

[@maradanikhil6882]

we can use "unordered_map" instead of vector for storing ,if there are negative numbers;

[@Sumeet_100]

but this still gives TLE ? isn't it ?

[@muditkhanna8164]

unordered map cannot be used for 2d size , you should use map, as the internal implementatin u_map is hashtables ,which is not working for 2d size, meanwhile map could give you TLE because of extra log(N) insertion tc

[@muditkhanna8164]

@@Sumeet_100 instead of using map , try to create a 2d vector and create a hashtable using this and fill the dp of pointers and indexes as target and ind , theoritically, it might work in 0(1),but its actually not 0(1), or you can create your own class just for simplified code.

[@kushjoshi9427]

unordered map stores key, value pair you can use pair as the key to store index and target but to store that we have to create a custom hash function or you could just make the 2d matrix 2 times the value if it is -ve store it after n

[@nodipankar677]

@@kushjoshi9427 we can use as unordered_map? isn't that correct?

[@chirlasowmyareddy]

Understood!! minor change for arrays containing zeros -remove target==0 condition and add this if(ind==0) { if(target==0 && nums[0]==0) return 2; if(nums[0]==target || target==0) return 1; return 0; }

[@mayurdas9738]

can u explain, how you came to this solution and how it is helping us to solve the error that we are getting?

[@anujrathore5726]

thank you buddy

[@kushalgupta2041]

bro your condition are correct but i think you forgot this case where you have not reached index = 0 but target is already achieved means target = 0 & ind != 0 but arr[idx] = 0 then you also have to count that case right so you have to also add this case: - if(target == 0 && arr[idx] != 0) return 1;

[@TON-108]

Thanks bro!

[@aryanmusicacademy944]

if(t < 0) return 0; if(ind == 0){ return (v[0] == t) + (t == 0); }; i did the same thing, the question stated "positive" values, but had 0 in the test cases.😭

[@divyanshbalisterverma1734]

Understood, even solved without watching video.... Best DP series on any platform.💯💯💯💯💯

[@subratsahai2017]

we can use map, understoodd

[@indraneel6601]

That was just amazing. I've actually done this problem from scratch without even watch this video which took me around 45 min(recursion, memoization, tabulation and Space optimization). Raj Sir you are just astounding

[@AshishGupta-bi4rh]

One thing to note here is that if the array had 0 also as its element then we can't return 1 from the base case if(sum==0) we have to go to index==0

[@satyamsingh7178]

So what should be approach

[@jeemains3524]

@@satyamsingh7178 class Solution{ public: int fun(int pos, int sum, int arr[],vector &dp,int N) { if (pos == N) return sum == 0 ; int &ans = dp[pos][sum]; if (ans != -1) return ans; ans = 0; ans += fun(pos + 1, sum, arr,dp,N); if (arr[pos]

[@aditianand6966]

best part "lecture seven is the most important in the whole universe"

[@goooo9561]

Codes that work even for multiple zeroes: Top Down/Memoization: Time complexity:O( n*sum ) Space Complexity:O( n*sum+n ) int helper(int arr[],int k,vector &dp,int i) { if(dp[i][k]!=-1) return dp[i][k]; if(i==0) { return 0; } int inc=0,exc; if(arr[i]

[@HoppyGamer]

Thank you so much was stuck on this for hours

[@ISHARAMTEKE-ku2ll]

Thank you

[@manishprajapati8544]

I done this question without watching this video in just 26 min. My concepts are getting crystal clear thanks Raj VikramAditya 🤩🤩🤩

[@aryankumar87771]

it's not "just" 26 min, this is a 10 min problem

[@mgfreefirelover4471]

I'm also brother do this problem without watching the video ☺️

[@manishprajapati8544]

@@mgfreefirelover4471 sahi hai bhai karte jao ✨

[@aryankumar87771]

@tokyo9570 to formulate the solution on paper - 5 min ( if never seen this problem before ), to code - another 5 min

[@anshumaan1024]

@Tokyo haha, bro its 1 min problem, depends on your typing speed🤭

[@animeshbarole]

Understood, even solved without watching video.... Best DP series on any platform.

[@anishkumarde5505]

For storing we can use a map... Where target and index will be converted to string and then store it as a key with values

[@nitishmishra9943]

we can also use array for index and map for target (every element of indexe's array will contain map)

[@rishabhgupta9846]

can you share the solution using map,I'm getting wrong answer

[@Sumeet_100]

​@@rishabhgupta9846 This code still give TLE #include const int mod = 1e9+7; int f(int i,int tar,vector&arr,unordered_map &dp){ if(tar==0){ return 1; } if(i==0){ return dp[0][tar] = (tar==arr[0]); } if(dp[i][tar]!=-1)return dp[i][tar]; int notpick = f(i-1,tar,arr,dp); int pick = 0; if(tar>=arr[i]){ pick = f(i-1,tar-arr[i],arr,dp); } return dp[i][tar] = (pick + notpick)%mod; } int findWays(vector& arr, int k) { // Write your code here. int n = (int)arr.size(); unordered_map m; for(int i = 0;i

[@namansharma5128]

for handling the cases in which the array contains 0 --> use only one base condition --> if(ind < 0) return tar == 0; or you can use--> if(ind == 0){ if(num[0] == 0 && tar == 0) return 2; if(num[0] == tar || tar == 0) return 1; return 0; }

[@VishalPatel_imvishal]

worked. thanks

[@spiral546]

thx

[@codermal]

map could be used for -ve integer case and btw understood💯

[@rishabhgupta9846]

pls share solution using map ,I'm getting wrong answer

[@_ANIKETVerma]

plese share the solution

[@adityabhoyar5693]

I think for negative integers we can take take the absolute value of the most negative integer and then do it like ele=abs(minvalue)+1 and then add this value to all the elements of the array as well as the target that we needed ,as the net difference between all the elements will be same .

[@rahulsrivastava9710]

I did it my own...got stucked but cleared 😊 Thank you Bhaiya @Striver Bhaiya

[@sujayshanbhag2055]

Understood!! minor change for arrays containing zeros -remove target==0 condition and add this if(ind==0) { if(target==0 && nums[0]==0) return 2; if(nums[0]==target || target==0) return 1; return 0; } P.S :- take you forward viewers make the best community :)))

[@abhishekpandey0295]

nice brother

[@VIRAJBHOSLE]

Here is the tabulation for edge cases: arr 0, 0, 0 and target 0 arr 0, 0 , 1 and target 1 public static int subsetSumToK(int n, int k, int arr[]){ int[] curr = new int[k+1]; int[] prev = new int[k+1]; prev[0] = 1; curr[0] = 1; if(arr[0]

[@RahulGuptaa29]

oh bhai GFG main 4 ghante se sir phod raha tha! thanks yaar

[@aasmohammad2651]

nice brother because i was trying to solve this problem on gfg

[@kgdfcr2347]

​@@aasmohammad2651 bro gfg pe case 104 galat aruha hai yeh logic ke baad bhi can u pls help

[@sagarbathla5160]

Hi Striver. Thanks for the great explaination. but i have one doubt why are we starting the nested loop of target from 0. It should start from 1 right. Since we already covered the 0 case in our base case.

[@rocklee3254]

watch his next lecture u will come to know about it

[@siddhiparsekar]

hey, i got the same doubt...did you get it why he started from 0 and not 1 like before?

[@VishalKumar-yc3wr]

Bhai explain kar do

[@shreyanshpatil8303]

start with 1 still it gives the correct output

[@pranavkumar1543]

@@VishalKumar-yc3wr We can have target as Equal to Zero, That's why we start from Zero for the target /sum loop

[@karanprabhakar72]

use map to save (pair of index target) Will work for negative cases One point to remember " this code wont work when the array contains 0 itself , hence a little modification is required Remove 0 from the nums array and change return statements when target == 0 , return 2 instead of 1 1 for the indexes taken 2 for the index taken + 0 added.

[@SasukeUchiha-jb6rf]

Hi Karan, can you elaborate how to use map for negative cases? Like how map works, I mean pair signifies what and what does second int parameter of map signifies? It would be of great help

[@karanprabhakar72]

@@SasukeUchiha-jb6rf pair of int and int First index from ( n-1 to 0) and other int represents sum formed so far

[@karanprabhakar72]

@@SasukeUchiha-jb6rf let ne add code for it

[@saunaknandi1814]

@@karanprabhakar72 can u send the whole code

[@girishbhargava6367]

Striver, I think you are referring to the usage of map. Please correct me if I am wrong... Your explanation is extremely intuitive.

[@mrinmoyhalder7293]

I also thinking same, but then in map, key will be pair and value in single int.isn't it ??

[@rishabhgupta9846]

can you share the code using map

[@HimanshuSingh-rm5sd]

@@mrinmoyhalder7293 we can use map like key will be for indexes 0 to n-1 and value will be a vector of int ie like columns in matrix or sum

[@GManiKarthik]

Wow, what an incredible lecture! 🙌 I’ve finally understood and even implemented the recursion, memoization, tabulation, and space optimization code myself! 💻✨ You delivered exactly what you promised at the beginning of this DP series. 🔥👏 #Understood ✅ #DP17 🚀 #HatsOff 🎩 #Striver 💯

[@naveenvebuthi8357]

For testcase num={0,0,0,0} tar=0 answer should be 16, But code generating output as 1.

[@keshavbiyani9202]

Thanks Striver for the lovely content man. Here's the condition needed to deal with multiple 0's in the array if index >= n: if sum == 0: return 1 else: return 0 Here's the complete python code class Solution: def recursive(self, arr, n, index, sum, dp): MOD = 1000000007 if index >= n: if sum == 0: return 1 else: return 0 if dp[index][sum] != -1: return dp[index][sum] notPick = self.recursive(arr, n, index+1, sum, dp) if arr[index]>sum: dp[index][sum] = notPick else: pick = self.recursive(arr, n, index+1, sum-arr[index], dp) dp[index][sum] = (pick%MOD+notPick%MOD)%MOD return dp[index][sum] def perfectSum(self, arr, n, sum): # code here dp = [[-1 for _ in range(sum+1)] for _ in range(n)] return self.recursive(arr, n, 0, sum, dp)

[@shivanshsingh176]

There is an important test case to be considered : num : 1 0 0 1, target = 0 If you will place the base conditions like if(j==0) dp[i][j] = 1 in the for loop, then it will be wrong. That's the reason that base case is not defined in the loop. I had a habit of defining everything in the loop so 2 of my test cases were not running. That I realized this, it sure took time to realise this !!!

[@Sakthivel-zq1hb]

A whole hearted Thanks for your Efforts. And I hope you would get recognised by the big Institutes and Industries 🙂

[@pawanharwani4598]

If there are non-negative integers and sum can also be non-negative then we can use map data structure but what if given array is arr[] = {0,0,0,0,1} and required sum is 0, in this case our code will return 1 as answer but the actual ans is 16. This case is occuring due to that base case condition i.e if (sum==0) return 1, so how will we handle this case.

[@takeUforward]

Thats a valid question, let mr address this in the next video.

[@Aks-47]

@@takeUforward sum==0 and ind==0 return 1; handles this!

[@bharathkumar5870]

ans is not 16,ans is 1 only..{0,0} is not a set it boils down to {1}

[@Aks-47]

@@bharathkumar5870 first understand the question, and then cross question.. This set is different from "set" data structure

[@shivangagrawal2923]

@@takeUforward solution?

[@niloychowdhury4729]

I did in this way.Just carry an extra arguement cur_sum and whenever the function calling reaches at it's base case(indn>>k; vectora(n); for(auto &it:a) cin>>it; vectordp(n,vector(k+10,-1)); cout

[@hashcodez757]

if facing wrong answers, that might be due to the inclusion of zeroes into the test cases. for example: [0, 5] if you'll try to draw a recursion tree then you'll definitely get it. According to the base conditions: if(target == 0) return 1; this will then and there only stop the further recursive calls even if the element might be zero which results in wrong answer. new Base conditions are: if(n

[@madhu_mohanreddy]

im still getting error can yu post the code

[@hashcodez757]

Recursive Code(not memoized and tabulated) class Solution{ public: int fn(int idx, int sum, int arr[]){ if(idx

[@Codebreaker0702]

@take U forward at 24:27 , we can also write base case as if(ind==0) return dp[0][a[0]] == true; . It worked for me.

[@RaghavSharma-nt3hr]

NOTE: CASE OF- if(target==0 && arr[0]==0) return 2;

[@codysaurabh]

Why

[@MukeshKumar-cc3uh]

We can use a list of map to counter the negative values in the array or a negative target. And maybe, there we don't have to check(before picking/taking), if the curr. value is less than target or not, as in future, there is a possibility of -ve ints. "Understood" Striver .👍

[@craftanddiy4773]

can u provide the code

[@dharmeshpoladiya9047]

Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥

[@himansh4812]

@32:00 We can use unordered map to store sum and index pair. When sum can be negative.

[@craftanddiy4773]

can u provide the code

[@GauravKumar-wk9tr]

Ther is Slight change u can make for 0s : 1-->Don't simply return if u reach to Target , go beyond even you reached target as there can be multiple Zeros that will Also make the another combinations 2-->while returning pick+notPick add a supportVal to it by checking if(target-arr[currIdx[)==0)supportVal++; it simply states that u can reach to the target at this index also so add 1 to your ans; int solve(vector& arr, int idx, int target, vector& dp) { if (idx == 0) return (target == arr[idx]) ? 1 : 0; if (dp[idx][target] != -1) return dp[idx][target]; int notPick = solve(arr, idx - 1, target, dp); int pick = 0; if (target >= arr[idx]) pick = solve(arr, idx - 1, target - arr[idx], dp); int supportVal=0; if(target-arr[idx]==0)supportVal++; return dp[idx][target] = (pick+notPick+supportVal) % MOD; }

[@SouravKumar-um7pr]

What is MOD

[@untitled6483]

So how this base case can be written in tabulation.

[@neptune25]

for multiple zeros change this base case if(nums[0]

[@anishpatro]

tq bro

[@zhunzargulhane6741]

what is wrong here with my code. Could you please help with it. public static int findWays(int nums[], int sum) { int[][] memo = new int[nums.length][sum+1]; for(int i=0;i

[@Anschlusss]

Understood!!! ❤❤❤. Just in case if anyone wanted the solution for negative numbers, Here it is.... #include using namespace std; class Solution{ public: int solve(vector arr,int sum,int index,map &dp){ if(index==0){ if(sum==0 && arr[0]==0) return 2; else if(arr[0]==sum || sum==0) return 1; else return 0; } if(dp[{index,sum}]!=0) return dp[{index,sum}]; int nottake = solve(arr,sum,index - 1,dp); int take = 0; if(arr[index]0) take = solve(arr,sum - arr[index],index - 1,dp); else if(arr[index]>=sum && sum

[@Surya-ej4zf]

if(sum==0 && arr[0]==0) return 2; why this line??

[@as.if_0077]

@@Surya-ej4zf watch the next lecture or else draw recursion tree

[@bhagatalisha]

Watching Striver is like getting your fundamentals at place!

[@johncenakiwi]

Raj, can you please also do a lecture on Longest Increasing Subsequence? You have already explained the tabulation solution on your channel but can we also have the recursive solution with the memoization solution where we use a 1D array for memoization? Thank you.

[@untitled6483]

Took me 3 hrs. to do recursion, memorization and tabulation. But I learned how I should write recursion, memorization to be able convert it to next step.

[@piyushsaxena6243]

understood , love ur explanation of each and every problem

[@srcodes13]

For anyone struggling with the test cases not passing, the constraints of the problem have been changed, the array can contain zeros now. Just go to the DP 18 video in case you need an explanation.

[@ranasauravsingh]

UNDERSTOOD... ! map data structure... ? for negative input integers... Thanks for the video... :)

[@Mr.codinghacker]

congrats for 500k subscribers bhaiya

[@PratikPatil]

unordered_map or map can be used to store the negative states of target

[@AlokLaha-te2pd]

Thanks Striver. Understood it very well. For negative indexes we can use map where keys will be pair of index, sum

[@mayankbharti531]

if you guys are getting 11/13 test cases passed in tabulation then try adding:- if(num[0] == 0) dp[0][0] = 2; after the given two conditions.

[@akarshitkumar6744]

thnx, i am searching for same problem

[@Noobdie2779]

Thanks it worked😊

[@CodeAndThrive]

yeah it worked! may u explain it?

[@yashrawat5158]

can you explain this?

[@varunsharma5582]

@@CodeAndThrive ​ @yashrawat5158 Because if very first element has value 0 and target is 0, it can contribute twice, once by taking it and once by skipping it. So, it can add value to two different kinds of subsets one that take it and ones that don't {0} also has a sum of 0 and {} also has a sum of 0, similarly if second element was also 0, there will be similar permutations and combinations.

[@shreyasnagabhushan4918]

we can use dictionaries to store DP instead of 2D array, if negative integers are present in array .

[@humbleGuy_1729]

We will get overlapping subproblems only when there are duplicate elements in the array (talking only for this particular problem)

[@tanmayrauth7367]

No thats not true. You get overlapping sub problem because for solving big problem you break it into pieces and then there is possibility that small piece might have been solved previously

[@humbleGuy_1729]

@@tanmayrauth7367 i was speaking only for this problem bro..

[@Flynn-lk8im]

⚠ If you are getting wrong answer on some test cases, the culprit is the 0s in the array. So final answer will be `ans + ans * number of combinations of n 0s`. The number of combinations of n 0s is just the nth triangular number i.e `n * (n + 1) / 2`.

[@rohitraj5832]

@Striver, you are missing here 1 thing, what if nums[0]=0 and target =0 .in memoization case. then from the first base condition it get returns but, it should increase subset count . bcz on adding 0 , there is no change in the target. but subset count changes. IN GFG your code is giving wrong answer. you code is not getting accepted because we are not doing "INCLUSION AND EXCLUSION on index=0" . plz reply.

[@sameera3839]

hey. what do you mean ?

[@ankurshahi9527]

Thank you Rohit, I was also trying to figure out what went wrong in the code. Base case: if(index < 0) { return target == 0;}

[@Steve-kv5we]

@@sameera3839 He means if we are at index 0 and target is also = 0, then we should return 2 not 1 because we can consider taking that 0 in our subset as well as we can consider not taking it in our subset and thus 2 different subsets will be formed including 0 and not including 0. Hence, we should return 2 in that case.

[@YVGamers]

@@Steve-kv5we thanks have a good understanding from this

[@tridibeshmisra9426]

why ? the question states that all the numbers are positive it means 0 is not included that's why striver has not done any mistake.

[@KrishnaGuptaTech]

We can use hashmap, that didn't even clicked my mind, Understood boss !!!

[@adityashrivastav4983]

Please provide leetcode link also

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@vaibhavdeshmukh7900]

I feel this code is not considering the case when multiple zeroes are present in the array. We can't directly return 1 when we encounter tar == 0; that won't consider zeros present in the array after the index when we got the sum ==0 while doing the recursion. EX Test Case where the above code will fail: n = 4, target = 3 elements: 0 0 3 3 PS: This issue has been discussed in the following video.

[@tarunkumar3279]

which video

[@HARSHPIPAL]

sir,you can directly write single base case for recursive part (if ind==-1) if(target==0) return 1; else return 0;

[@kushalgupta2041]

brother but in this case you are increasing time complexity quite right? because when you find target you have to iterate over all not take possible sum of it till you reach idx == -1 right? so why don't we do this:- if(idx == 0) { if(target == 0 && arr[idx] == 0) return 2; if(target == 0 || target - arr[idx] == 0) return 1; return 0; } if(target == 0 && arr[idx] != 0) return 1;

[@aryanrastogi1335]

if sum will negative we can use map.

[@KapilSharma56419]

// Handling the first element of the array separately if (arr[0]

[@dishagupta7446]

In case of negative numbers we can use hashmap

[@iamnoob7593]

yes

[@arvindjaiswal8013]

Use Map where the key will be and the value will be the state of the sum.

[@craftanddiy4773]

can u provide me the code

[@Steve-kv5we]

Understood 💯💯 The Memoization code to handle subsets containing 0's -> public static int Memoization(int idx, int[] arr, int target, int[][] dp){ if(idx==0){ if(target==0 && arr[0]==target) return 2; else if(arr[0]==target || target==0) return 1; else return 0; } if(dp[idx][target]!=-1) return dp[idx][target]; int notTake = Memoization(idx-1,arr,target,dp); int take = 0; if(arr[idx]

[@saunaknandi1814]

steve can u make me understand this if(idx==0){ if(target==0 && arr[0]==target) return 2; else if(arr[0]==target || target==0) return 1; else return 0; }

[@rishabhgupta9846]

@@saunaknandi1814 here we are not using if target==0 return 1 as the base case ,because if we use then it will return without coming to index 0 then we are avoiding the 0 present at index 0.But if we above condition. Then it will go till index 0 and check of target is 0 and value at index 0 is 0 then return 2 for else if target== 0 then return 1 or if current value(value at index 0)is equal to target then return Else return 0

[@AmitPrajapati-ul4ei]

@user-ht9fr8sd8u op vai

[@romanreigns4235]

@@rishabhgupta9846 thanks bro 😊

[@theunknown1333]

for handling zeroes, since k>=1 we can sort in decreasing order...and just write the same code and it will handle all the zeroes.... ::)

[@himanshuagrawal8012]

We can use UNORDERED_MAP to handle -ve values as we dont need our keys to be in sorted order, so O(n*m) space complexity will be there.

[@7akon]

I think an ordered map would be used. An unordered map wouldn't support a pair as a key. We need a pair as key as the key pair is (index, sum). An ordered map however will support it.

[@codingwithanonymous890]

@@7akon right

[@priyak8786]

@@7akon yeah

[@parthsalat]

@@7akon Thanks for the hint

[@ankursingh8296]

But what will be the base case

[@riderpd09]

Bhaiya subset wale problem mai take nottake wala meta itna achha se samajh gaya hu ki ab apka videos 2x mai bhi full samajh mai araha hai :))

[@shobhit351]

Love all videos but 1 suggestion Pls at the end mention the best time and space complexity in which a ques can be solved (which may not be attained by DP, but just mentioning it will help as i can search and study that best method which will help me interview )

[@ayushnath3768]

the last code is the most optimized one

[@Code_With_Goat]

small correction here : if( a[0]

[@sahilgoyals]

map data-structure in c++ for handling -ve sum

[@SasukeUchiha-jb6rf]

Hi Sahil, how can we use map for -ve sum? Can you elaborate with a example

[@sahilgoyals]

@@SasukeUchiha-jb6rf we can use map for any type of key as well just convert all the changing parameters to string amd store them Eg: Changing parameters are i and j String key = to_string(i) + "-" + to_string(j); And them in unordered_map

[@DeepanshChawla_]

@@sahilgoyals we can use nested maps as well 😊 but i know that will add up the tc 🙂

[@SarvanShivani234]

indeed taking us forward😊

[@sunilpanchal1498]

Understood, and we can use unordered_map for negative values.

[@naamhaii]

unordered_map u;

[@BharatiSubramanian99217]

Hey understood. Just 1 question, why are we starting from sum=0 @ 32:23 ? I tried starting from sum=1, it failed a test case. Can you please help mw with this?

[@vinita3402]

same doubt

[@vanshsehgal9475]

Rather than using maps,we can do some mathematics and find the most negative sum that we would ever get and then adjust the size of mat accordingly. Like if most -ve sum is -100, then we can add 100 to our most positive sum we can get and everytime while accessing sum in the matrix, we will always write [sum+100], so that -ve sums are also handled, but yeah there can be issues regarding matrix size, it may become large enough that we can't even use it for memoization. But yeah its a way we can apply.

[@mayanksinghal9315]

For anyone facing the problem with {0, 0, 1} scenario. They can use shifting of index explained in video DP25 - LCS.

[@anveshkarra3861]

i think we can use hash map for negative numbers

[@omkarpatil5045]

Excellent!!But small correction in the base case that is if arr[0]==0 then there can be 2 possibilities hence.. if(arr[0]==0){ prev[arr[0]]=2; } else if (arr[0]

[@jayantgoyal3311]

is your code submitting correctly on code studio? mine is getting partially accepted

[@jayantgoyal3311]

Done. i forgot to take modulo with 1e9+7

[@niravsingh4532]

The linked problem is different.

[@ankitsagar8379]

At 24:39 , Shouldn't it be : Only if a[0] == target, then only my dp[0][a[0]] could be 1, and not a[0] LESS THAN and equals to target. If my target is more than or less than the 0th element i can't achieve it. Or does it signifies if don't include any elements only for first element it will be 1, considering it should not exceed the target value. Please clarify

[@meetsakhareliya755]

dp[i][j] shows sum=j is can be obtained with array till ith index. Now if our target is 5 out dp array column goes from 0 to 5. if a[0]=2 then a[0]

[@yoginpahuja5557]

arr=9,7,0,3,9,8,6,5,7,6 target =31 it fails correct output =40 it gives 37 Please update the correct solution

[@parushgarg4512]

is you able to find the mistake?

[@sahilgagan2242]

i got correct answer

[@dhanushb5203]

You should handle the zeroes, the explained code in this video works only on arr[i]>0. Lets talk about your testcase. Assume you have no '0' in your input, then you will get ans as 20. Now include '0', i.e adding element '0' to 20 subsets. Final ans = 20 (without zero) + 20 (with zero) = 40. Hope it clears your doubt.

[@shahrukhansari7806]

Sort the array

[@Steve-kv5we]

Yes, you are right it will give wrong answer in cases of 0. public static int Memoization(int idx, int[] arr, int target, int[][] dp){ if(idx==0){ if(target==0 && arr[0]==target) return 2; else if(arr[0]==target || target==0) return 1; else return 0; } if(dp[idx][target]!=-1) return dp[idx][target]; int notTake = Memoization(idx-1,arr,target,dp); int take = 0; if(arr[idx]

[@RitamSharmaBBB]

In the recursive code that is given below we would only find the subsequences with sum K. because the ind is going only in one direction (n-1 to 0). however the question states "subsets". for eg. for the array {1,2,3,7,8,9} with k = 11, the given algo would find only consider the subset {7,3,1} but not {3,7,1}or {1,7,3}. then why are all the testcases passing ?

[@anshulkumarneekhara9377]

subsets are always in order.

[@karthikmohan79]

web/app Dev guys: DSA, CP is overrated. Complex projects exists: Searchs internet,stack overflow ends up with no solution. DSA CP guys: here you go.

[@sumitpadadune3763]

understood sir thanks for such great series on DP

[@AvishekChatterjee]

UNDERSTOOD but @take U forward why are we making so much mess in the base case we can simply write if (index < 0) { if (sum == 0) return 1 ; else return 0 ; }

[@bishnoi6409]

then you cannot write tabulation method easily.

[@yashshukla1637]

Awesome Video Brotha!

[@ShahNawaz-cx3pi]

*********** Iterative Code for the count number subsequence whose sum is k ( & 0

[@ranjeet_sohanpal]

For the test {0,0,1}, just put dp[0][arr[0]] = 2, this will make sure both the pick and notpick are considered when the first element is zero.

[@harshwardhanpatki846]

Understood 🔥🔥🙏 thank you very much for your hard work🛐

[@muntajir646]

Base Case Correction : if (idx == 0) { if (tar == 0 && num[0] == 0) return 2; if (tar == 0 || tar == num[0]) return 1; return 0; }

[@tanoy54321]

still it's failing for 3 4 0 1 3 test case

[@ShubhamKumar-re4zv]

Base case is incorrect It should be if(index==0){ if(sum==0) return 1; return 0; } Other wise for arr{1,0,2,3} this code will give output 3 but the correct output is 4. Article of this problem is also incorrect ,There should be a option to add comment to the article or any other way to inform about the incorrect code

[@muntajir646]

Large test cases are not passing in coding ninjas for Recursion + Memoization. Do this private static final int MOD = (int)1e9 + 7; return dp[i][tar] = (pick+not_pick) % MOD;

[@dhruvkaran9724]

thanks striver i am able to solve DP problem on my own ... feels like apun ich bhagwan hai

[@vaishnavip4808]

@takeUforward.Just a little curious, now since we have a positive values in the array.,starting the possible sum values from 0 to K suffices.If there were negative values, we don't have a bound for k.Can we still see overlapping subproblems.Ideally k could be anything from -infinity to +infinity. Would dp work in such a case.

[@divyanshbhatt8273]

we can use a matrix of the size of the range of nums[i] limit + 1 if they are negative numbers and for every sum we are going to add the max limit to the sum and then return accordingly i.e dp[n-1][target + maxlimit]....

[@nissarhussainnooranishaik665]

Can anyone tell me why the sum is starting from 0 in tabulation, when it's been taken care of in base case?

[@arnavdubey1904]

did u get the answer bro ??? i m having same doubt

[@TheDebuggers-fx9vp]

i thnk a sligh change in base case can handle all the case well,instead of returning when we encounter the target to 0; if we keep exploring until the end of the tree then we can get our desired result class Solution { public: int helper(int arr[], int n, int sum, vector& dp) { // Base case: If there are no elements left if (n == 0) { return (sum == 0) ? 1 : 0; } // If the subproblem has already been solved, return the stored result if (dp[n][sum] != -1) return dp[n][sum]; // Compute the result for this subproblem int notPick = helper(arr, n - 1, sum, dp); int pick = 0; if (arr[n - 1]

[@krishgupta4408]

if your array contains 0 then you can add an extra condition :- if(sum==0 && arr[0]==0) return 1;