9 Count of Subsets Sum with a Given Sum

[@suyashdubey520]

bhai ek video pen ghumane par bhi bana dena

[@TheAdityaVerma]

😂😂

[@svworld01]

@@TheAdityaVerma maine kosis ki bahot bar ghumane ki but failed :(

[@amansharma7865]

bhai uske liye jee ki coaching leni pdti hai...udhr seekh jate hain pen ghumana apne aap 🤣

[@nikhilnaidu1383]

@@amansharma7865 hahahha

[@amanwatts24]

​@@TheAdityaVerma For every new DP problem first we should write recursive code and then convert it to bottom up approach ?

[@noobichesser9434]

Engrave this in stones and history will witness that best ever tutorials created for Dynamic Programming on entire planet was created by Aditya Verma. Period.

[@ytg6663]

Ok

[@AniketSingh-nx4ds]

striver better now

[@anonymousanonymous7507]

​@@AniketSingh-nx4dsno

[@shivendrasingh8520]

@@AniketSingh-nx4ds bhaiya abhi bhi aditya verma is best in terms of dp bhai

[@30sunique78]

Everyone have different perspectives. If it's not best then What's doing here Dude 😂 ​@@shivendrasingh8520

[@shadowofthecorpse9481]

Thanks for this DP series Aditya! Great tutorial but I spotted one small potential mistake in the initialization part at 10:40. The problem is, that initializing the entire column with 1 will work only if the input array has all non-zero elements. As me and a few others have pointed out, the method fails when the input array has any zeros. For eg: n=3, sum=0. We can have a set here as {0,1,2}, so there'll be subsets of {} and {0} possible hence count will be 2. This is true for multiple other input arrays where actually count >1 for sum=0, but we initialized count=1 for all input arrays when sum=0. Here's a small fix I found to the issue: We initialize the first column of the array acc to the formula: 2 ^ (no of zeros in the array at that size). Hence, for eg: arr={0,0,1,0}, sum=0 For n=0, value will be 2^0 = 1, i.e {} For n=1, value will be 2^1 = 2, i.e. {} and {0} For n=2, value will be 2^2= 4, i.e. {}, {0}, {0} and {0,0} For n=3, value will be 2^2 = 4, i.e. {}, {0], {0}, and {0,0} For n=4, value will be 2^3 = 8 i.e. {}, .............., {0,0,0} Reason: In the sum of subset problem, we simply needed to return whether or not a set exists for sum=0, which was always True as empty set {} was always existing. Here, we need to return count of subsets for sum=0 (for first column), which will include all possible subsets in the array which add up to 0.

[@jyotijangid5243]

can you share the link of the code here? I am getting the wrong number of counts.

[@shadowofthecorpse9481]

@@jyotijangid5243 Sure, it's in Python: def find_zeros_in_array(arr): return len([x for x in arr if x==0]) def count_of_subsets_with_given_sum_corrected(arr,n,W): K = [[0 for x in range(W+1)] for x in range(n+1)] for i in range(n+1): for j in range(W+1): if i==0 or j==0: if i==0: K[i][j] = 0 if j==0: K[i][j] = 2**find_zeros_in_array(arr[:I]) #the only line that's different from the video elif arr[i-1]

[@ravishekranjan7282]

Thanks man for this observation

[@jyotijangid5243]

@@shadowofthecorpse9481 Thankyou

[@ironmonk4074]

I think he mentioned it at 12:42 that this solution is only for the case when all the numbers are positive in the given array. Still great solution for the case of including a zero.

[@ankitsablok952]

This lecture series is going into a hall of fame for all things algorithms. Watching your videos is synonymous with watching a movie. What a flow and what a way of presenting the information. Dude man you deserve to be a teacher of CS concepts, open an NGO bro or keep uploading such stuff. One word to sum it all #AMAZING!!!!!

[@0anant0]

9 of 50 (18%) done! I think need more explanation as to why we consider if (cur_elem

[@priyalagarwal9996]

Definitely true when you said - "Yaar aisi problems krne mai kitna maza aara hai!!". Finally now my DP-phobia is going away and i am actually enjoying your videos!! Thank you bro :)

[@samirpanday4898]

dp-phobia is real . repeat after me.

[@kaushalmzp]

same here

[@vibhu613]

@@samirpanday4898 sahi hai.....

[@rishabhjoshi3092]

hi, i am new here, he explains the concept, but what about coding? we have to do that ourselves? which language he uses in videos , c++ or java?

[@arfaatsyed6853]

@@rishabhjoshi3092 hello, he just explains to generic code to solve the given problem. You can apply them any language. If you're using java you can replace some of the code with java methods. But the code he explains in any language Is more or less the same

[@ShubhamKumar-rv5qh]

I was literally waiting for something diff. but the next moment you said " HO GAYA BHAI"

[@saptarshibose9718]

I have tried many DSA related videos but frankly speaking, you are the king of DSA for teaching the subject easily. Because of you now DP or DSA looking like a piece of cake.!

[@rajatgupta7488]

17:18 !!!! Ultimate Swag !!!

[@akhiljain1695]

I'll definitely share this channel of yours, because the explanation is just beyond amazing. Request you brother to keep making such videos.

[@rishabhjoshi3092]

hi, i am new here, he explains the concept, but what about coding? we have to do that ourselves? which language he uses in videos , c++ or java?😊

[@akhiljain1695]

@@rishabhjoshi3092 My suggestion would be to pick Java or Cpp and try coding few problems initially and using standard libraries that provides data structures and algorithms. Once you code out a few problems. You'll get a hang of it and all you will then need is the logic which this guy is serving in an unmatchable way.

[@mohit84604]

@@rishabhjoshi3092 c++

[@bavarvaneel5]

Me: "I'm not able to understand DP" Professor: "You are dumb!!!" Lee Aditya Verma: "Hold my beer🍺"

[@tejasasthana6951]

*aditya verma: hold my pen

[@AvikNayak_]

@@tejasasthana6951 no hold my camera hoga agar pen de dega toh likhega kisse

[@aptitudepointiit-bhu5358]

Awesome explanation. Bhaiya you have only considered the case for positive elements. If zero/es is/are also present in the array (as it is in gfg question), then we need to iterate: for(int i=1;i 0) => dp[i][0] = dp[i-1][0] else If(arr[i-1] dp[i][0] = dp[i-1][0] + dp[i-1][0]; and this extra term will lead to extra +1. And this extra +1 will exist whenever arr[i-1] == 0. Thus increasing our answers by no. of zeroes whenever required.

[@sarthakbhatia7639]

Right in that case I think we can initialise it to number of zeroes as it will be equal to the number of subsets.

[@yashrajpathak8103]

sir big fan

[@varshikjain1862]

what is the value of 'm' here in if(arr[i-1]>j) dp[i][j] = (dp[i-1][j])%m;

[@fardeenalam6929]

@@varshikjain1862 10^9 + 7

[@harshitewari]

needs to be a pinned comment!

[@purut5105]

"Han bhai bs khatam hogya !!!" Apka ye line maja hi ajata h . Thank you so much Aditya , now I'm Loving DP!!!!!!

[@himanshukaushik948]

Hamesha shochta tha ki koi senior mentor mil jae. Aaj mil gaya bhai. Bhot shi videos h

[@avadhoot05]

📢📢Aditya's solution will fail for testcase that includes 0s in input array. While initialization, in case of sum == 0, he is directly considering that only empty subset exists hence he is storing 1 in first column. But consider, input arr= [0,0] and sum = 0. here we CAN'T initialize first column with 1 since for sum = 0, subsets are {0(0th index)}, {0(1st index)}, {0,0} , {}. i.e. count 4. The only change will be to use if(sum == 0 && n == 0) then assign 1. (THIS CONDITION IS IMPORTANT) if(n == 0) then assign 0 and rest will be handled by pick/no pick algo. Thanks!! and overall great explanation by Aditya Verma💯💯

[@aarchigandhi6617]

Thankyou so much!! It helped me:)

[@manavjain4453]

Thankyou so much. this one important condition used up a lot of my time.

[@ramrana5257]

2 GODS who use DP snax Aditya verma

[@smitchaudhari9783]

Underrated comment 😉

[@miteshbhuptani5542]

tushar roy

[@manikantareddy7595]

Bhai Aap OP biroooo.

[@prateekarora4549]

snax kon hai??

[@nikhilnaidu1383]

@@prateekarora4549 pubg player hahaha

[@rupesh_dharme]

I think in initialization we should only initialize the first row with 1 at (0, 0) and start second for loop with j = 0, because initializing the first column with all 1's might give the wrong result if there exists a 'zero' in the array. Input for which this initialization do not work: n = 10 sum = 31 9 7 0 3 9 8 6 5 7 6 Correct me if I am wrong.

[@sigmarules7504]

correct

[@architarora-iiitd3265]

*Important point which is missed in the video* int perfectSum(int arr[], int n, int sum) { // Using DP int dp[n+1][sum+1]; int N = n+1; int M=sum+1; int mod=1e9 + 7; //Initialization for(int j =0; j

[@hemang10]

@@architarora-iiitd3265 Your argument is correct. but we don't need to initialize the array the way you said. Just initialise the first column with 1s. Then, just start the inner loop of j with j=0, as pointed out by some of the other comments. This will do the needful. The values of the first column will automatically get updated as the iterations proceed. so there is no need to manually check the number of zeros.

[@architarora-iiitd3265]

@@hemang10 Yes, correct. I just wanted to highlight the point that what does initialising the first column to 1 denotes.

[@stellararts9926]

@@hemang10 Thankyou! Great explanation

[@devanshishah1004]

I was looking for good DP series since last 1 year. Finally found this one. Best series ever. Can never thank you enough!

[@akshatsahu8021]

I watched your video, tried the question on gfg, it got submitted.. I was happy.. Then I realized that I did a mistake, I came back to your video and corrected by mistake of forgetting to give it a LIKE. You are awesome bhai..

[@rajenderpassi9831]

For those who are wondering about why the problem is not being submitted on GFG. Here is the solution:- int perfectSum(int arr[], int n, int sum) { int t[n+1][sum+1]; memset(t,0,sizeof(t)); int cnt=1; t[0][0]=1; for(int i=0;i

[@abhayjoshi362]

didnt quite get why its happening can you elaborate or explain with eg ?

[@shubhammahindru3563]

@@abhayjoshi362 , The reason is when you have an array like 9 7 0 3 9 8 6 5 7 6, you have to consider 0 also as an option to make the subset whose sum is 0, so just calculating the values for j=0 rather than just initializing it as 1. While using index as j=1 0 TO 31---> 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 2 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 2 2 0 2 0 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 3 2 0 3 0 0 0 4 0 2 4 0 2 0 0 0 2 0 0 2 0 0 0 0 0 1 0 0 0 2 1 3 2 1 3 0 0 2 4 3 4 4 3 2 0 0 4 2 2 4 2 2 0 0 0 0 1 0 0 1 2 1 4 2 1 3 2 1 5 6 4 7 4 3 4 4 3 8 6 5 6 2 2 4 2 0 0 1 0 1 1 2 2 4 2 2 5 3 5 7 7 7 9 5 8 10 8 10 12 9 9 10 5 10 10 7 0 0 1 0 1 1 3 2 4 3 2 6 4 7 9 11 9 11 10 11 15 15 17 19 18 14 18 15 18 20 19 0 0 1 0 1 2 3 2 5 3 3 7 7 9 13 14 11 17 14 18 24 26 26 30 28 25 33 30 35 39 37 While using index as j=0 0 TO 31---> 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 2 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0 2 2 0 2 0 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0 4 2 0 4 0 0 0 4 0 2 4 0 2 0 0 0 2 0 0 2 0 0 0 0 0 2 0 0 0 2 2 4 2 2 4 0 0 2 4 4 4 4 4 2 0 0 4 2 2 4 2 2 0 0 0 0 2 0 0 2 2 2 6 2 2 4 2 2 6 6 6 8 4 4 4 4 4 8 6 6 6 2 2 4 2 0 0 2 0 2 2 2 4 6 2 4 6 4 8 8 8 10 10 6 10 10 10 12 12 10 10 10 6 10 10 8 0 0 2 0 2 2 4 4 6 4 4 8 6 10 12 14 12 14 12 14 18 18 20 22 20 16 20 16 20 22 20 0 0 2 0 2 4 4 4 8 4 6 10 10 14 18 18 16 22 18 24 30 32 32 36 32 30 38 34 40 44 40

[@namansharma8586]

thanks bro!

[@saurabhsoni738]

thanks bhai

[@amitkarn1888]

public static int findWays(int nums[], int sum) { int N = nums.length; int[][] mat = new int[N+1][sum+1]; mat[0][0] = 1; int mod= (int)1e9+7; for(int i = 1; i < N+1; i++) { for(int j = 0; j < sum+1; j++) { if(nums[i-1] > j) { mat[i][j] = mat[i-1][j]; } else { mat[i][j] = (mat[i-1][j-nums[i-1]] + mat[i-1][j])%mod; } } } return mat[N][sum]%mod; }

[@LivenLove]

Really appreciate the level of mastery you have.. thumb rule yehi hai ki agar koi kisi aur ko concept samjha sakta hai toh his concepts are super strong, warna possible hi nahi hai.. baki log direct code likh dete hai pura ka pura phir walk through karenge.

[@akshatkumar2960]

while solving this problem on gfg you will encounter test cases where they have also included 0 in the array, so in order to tackle that scenario, only fill the first row for base case. Next start filling following rows using the technique of include/not include. As for ex: if there is only 0 in array then as per base case the ans will be 1, however actually ans has to be 2: 1 empty subset and 1 subset with 0

[@harmansinghsaini9515]

can you provide solution as it still not working

[@sohanshrungare8930]

thankyou for this comment and the explanation

[@beingnitian2745]

@@harmansinghsaini9515 j ko zero se likho code likhthe time thats it

[@avinesh8350]

If 0 in the array then just reverse the array in descending order.

[@surajkumar9756]

@@beingnitian2745 kaam ni kr raha hai

[@AkGautam_1904]

Sach bta rha hu aisa content kahi nhi milega❤️. Really your way of teaching is awesome.🤩🤩🙌🙌🙌 Thanks a lot sir🙏🙏

[@prachipardhi6324]

Thankyou so much for making these videos ......they have made me fall in love with DP ...........I love your way of teaching ..

[@AyurvedaAddict]

20:31 apka aadesh sar aakhon par sir ji ..... Greatest Explanation.........

[@ameerulshah4098]

We can use this same code for subsetSum problem as well And if value of final grid(t [ n ] [ sum ]) is > 0 return true.

[@VishalSharma-hq5ti]

Yes, but that would be bad as it will take more memory(bool - 1 Byte, int - 4 Bytes).

[@devendrasingh4776]

True but overkilling..

[@abhisekhagarwala3115]

I just want to appreciate your hard work. Initially I was skeptic about your video . Then i was facing issue with solving problems. Then one Friend recommended me your videos. Rest i first watched your recursion playlist. And now I am watching this series. You are great man.

[@koustubhmokashi4047]

I can see the difference between just a tutor and developer + tutor, and you fall into 2nd category, it's really difficult to explain these concepts , but you did it very well

[@lakanavarapunagamanikantaa7299]

for reference see this i do this after watching this video def path(arr,s,t,count=0): if s

[@rishabhmishra2760]

Amazing explanation brother I never see this type of explanation in my coding history!

[@Udayyadav-zg6nl]

Make videos on graph , backtracking and window sliding please. I like your approach towards concepts..You will rock Big bro .

[@rahulagarwal4874]

Brother, i can't tell you how much important this lectures of DP are for me. Thank You so Much..

[@shivambhanu2757]

Concept ki feel aa rahi hai bhai. Thanks a lot.

[@intelligentprogrammer]

I have one doubt in this video, Before this video or before using '+' , I was able to think of the changes like instead of T/F, we use 0/1 but regarding '+', I am not able to understand completely how we have used '+' by replacing '||'. If anyone knows ,then let me know too.

[@vishalvishwakarma8276]

I know what you are going through but I'll tell you to draw the matrix and fill it code wise, although aditya content is great, try pep coding's "Target sum subset" then perform the code on a paper, you will get a clear idea what's happening inside.

[@hasansayeed2155]

vishal vishwakarma in the subset problem aditya used t = t[i][j-wt[i-1]] || t[i-1][j] But here he used t = t[i-1][j-wt[i-1]] + t[i-1][j] t[i] / t[i-1] which one is corrrct we include the element in our set?

[@akash-lz2dq]

dekh bhai tu startting se 4th element pr hai or ab tu chahta hai no of ways ki subset sum given sum ke braber ho jaaye toh, vo tarike jnme is 4th element ko include krke given sum mil rha hai + vo tarike jinme is 4th element ko include na krke bhi sum mil jaa rha hai, vo total hoga

[@shivamtiwari3672]

if u have solved this problem using recursion before so it will be easy to understand bcz in recursion we call function 2 times 1st time we dont add element and in 2nd function we add element so when the added sum becomes equal to desired sum we do count++,so basically we are adding the count of both function called.

[@vishalvishwakarma8276]

@@hasansayeed2155 t[i-1] is the correct one, aditya did it wrong accidently. the explaination is that i = 1, represents wt[0], which makes it wt[i -1] to access each element of the given 1d array;

[@geeteshpopli5285]

I fell in love with DP because of you Thanks :)

[@yashmishra5796]

Should we bow!! Yeah Aditya Bhaiya Is a King!!!!

[@parulsinghal8573]

@Aditya Verma , Would you also upload a video where we are printing all these subsets as well .

[@gamerhu7462]

using recursion would be better ig

[@Kuriocity]

static void findUniqueSubsets(int[] arr, int n, List temp) { println("temp (to add)! " + temp); //println("#" + list + "#"); if (n == arr.length) { println(n + ":" + arr.length); list.add(new ArrayList(temp)); println("#" + list + "added #"); } println("#" + list + "#"); if (n < arr.length) { temp.add(arr[n]); println("temp after add " + temp); findUniqueSubsets(arr, n + 1, temp); temp.remove(temp.size() - 1); println("temp after remove " + temp); findUniqueSubsets(arr, n + 1, temp); } }

[@amansrivastava1332]

2 points i would like to add - 1-For those getting problem with multiple 0s, just start the column loop with j=0 instead of j=1 like this. for(i=1;i

[@DeepakSoni-zq5rd]

why we use t[i][j]= t[i-1][j-arr[i-1]] + t[i-1][j]; instead of t[i][j]= t[i][j-arr[i-1]] + t[i-1][j];

[@coldfinger3472]

@@DeepakSoni-zq5rd bro i resembles N(number of items) , either we include the item or exclude, we have considered the item, so in every case i will decrease.

[@karanrocks4447]

But marked t[0][0]=1.. Then only above code will work

[@atv8992]

why we getting error when using j=1 ?

[@vibhugupta3331]

@@atv8992 why j starts from 0 becoz in a given array we might have an element 0 which might gets missed out in case when j starts from 1

[@ganavin3423]

U win so many hearts....the reason for this is ur knowledge and helping nature.. Thanks bro!

[@ankitadalmia2078]

The way you find correlations between dp problems is amazing.

[@vamsimudaliar8643]

Could you please upload combinatorics problems . Worth watching ur videos. Its a very unique channel. Keep Going Bro !! . U earned a subscriber !!

[@TheAdityaVerma]

Will try

[@sreeraghuvardhanvangipuram9547]

For the 0 edge case in GFG, I found an alternate way to deal with it. Ex: 2, 3, 0, 1 Our function calculates all possible calculations for elements before it. This means possibilities are calculated only for 2,3 as they come before 0. Possibilites with 1 are left out and ans is lesser. Hence if we shift all the 0's to the end we ensure to calculate all the possibilities. That is what i did. Add this at the beginning int[] temp_arr = new int[n]; int ind = 0; // The problem came when 0's are dealt before other elements which // meant that we calculated 0s permutations for a smaller subset // meaning the answer would decrease // By pushing 0's to the end, we ensure that the all permutations // of 0's are calculated thus giving us the right answer for(int i = 0; i < n; i++){ if(arr[i] != 0){ temp_arr[ind++] = arr[i]; } } for(int i = 0; i < n; i++){ arr[i] = temp_arr[i]; } Also do modulo 1000000007 when you are calculating t[i][j].

[@MdKais-lf6wj]

vai,plz make a playlist on "GRAPH THEORY".please vai

[@rahulchudasama9363]

bhai genius tu, What a simple way u are solving problem..

[@MOHITPATIDARRA]

A wonderful course given freely by GOD of DP. Thanks very Much Sir for providing Amazing Content.

[@nihitjain3677]

agar array mai 0 bhi diya ho toh , sirf first row par hee lagana aisa 1 0 0 0 0 0 0 baaki ka leya loop hee chalana j=0 se chalega na ki 1 one se REASON ( agar array mai 0 bhi hai toh no of ways with sum=0 badh jayega {}, {0}, {0,0,0} isme jaise 3 ho gya

[@sauravkumarsonu829]

True definition of Teacher, Aditya Sir, salute for your contribution. Apki wajah se aaj ham jaise log v aaj dynamic programming ko shi tarike se sikh rahe🙏❤️

[@ShivamKumar-hf5ec]

// there is some modification required in the aditya's code that is the number of subsets of sum == 0 // the subsets will be the 2^i where i is the number of zeroes present in array till a given index . // you can also map the number of zeroes with the index this will reduce the complexity int count_zeros_till_index(int arr[],int i)//returns the numberof zeros in array till index i { int count=0; for(int j=0;j

[@hemankpandya989]

exactly..........because element can also be zero........😁

[@hemang10]

I think we don't need to initialize the array the way you said. Just initialise the first column with 1s. Then, just start the inner loop of j with j=0, as you have done in your code. This will do the needful. The values of the first column will automatically get updated as the iterations proceed. so there is no need to manually check the number of zeros.

[@WizBoyYt]

@@hemang10 Yeah, Counting will increase TC. Instead this multiply by 2 to last index's element

[@user-jp9jd6el1f]

constraint in a problem sum can't we 0 if u study problem carefully

[@xsuritox1058]

17:19 OOOO bhai, aise swap hote hai pen fingers k beech, Aditya Bhai OP🔥🔥🔥

[@tridevthakur7711]

Ur teaching style is awesome & plz make video on "LIS" and "kadane" using Dp

[@pavankaranam7469]

best dp series.Period.

[@tkishore1260]

Bhai u r really amazing 👌👌.itna acha kaun padhata hai... 🙏🙏

[@JacobAbraham-twozerosix]

Sir... Thanks for these video's. Your explanations are really good. I have one question. if we have a arr with zero's in it, for example arr = [0,0,0,0,0,0,0,0,1] and S = 1. The top-down approach gives me just 1, but the correct ans should be 256. How do we initialize the t when there are zero's in the array?

[@pratikkedar9979]

try arr = [1,0,0,0,0,0,0,0,0] and S = 1 you get 256

[@shadowofthecorpse9481]

@@pratikkedar9979 no you're changing the question. Even I have the same doubt as jacob

[@harshittrehan6232]

@Jacob Abraham the reason you're getting the wrong answer is because when we initialize the 1st column, t[i][0], we put 1 in there because in 1st column sum = 0 and an empty array sums up to 0, right ? But with zeroes, we can't put 1 in there. Because, consider this example: {0,0,0}, sum = 0 (1st column). Now, when i=0 (that is empty array.) then we put t[0][0] = 1. Makes sense. Now, i=1, i.e., elements = {0} and sum =0. The answer here is not 1 now. It is 2 because: {} -> empty subset sums up to 0. Good. {0} -> this subset also sums up to 0. Now, see i = 2 i.e. elements = {0,0} {} -> sums up to 0 {0} -> sums up to 0 {0} -> sums up to 0 {0,0} -> sums up to 0. Total 4! So we have 2 zeroes in the array till index 'i', so value is 2^2 = 4 Finally, i=3, elements = {0,0,0} => 3 zeroes => 2^3 = 8 subsets possible. Basically, for every index 'i' in column 0, you need to check the number of zeroes in arr[0...i-1] and then put the value 2^(number of zeroes in array till index 'i') in the cell.

[@ritish_sehgal]

This question assumes that array consists of only natural numbers, otherwise our Initialisation for first column would be wrong!!!!

[@gauravmaurya2599]

@@harshittrehan6232 awesome explanation bro..

[@taniyagupta840]

Please bhai, Graphs pr bhi video bnao. Keep up the good work. Thank You :)

[@ayushbhardwaj6783]

Thanks a lot Aditya. I was looking for videos to help me understand how to think DP way..!!! You immensely helped me. :)

[@gauravpareek3783]

Bhai what a content you have created...hats off to you! For this particular question we could do it by having the same matrix as for subset sum right? and then count the number of Trues present in t[i][10] and that should give us count of subsets? Is my understanding correct here?

[@adarshsrivastav3991]

These videos are so good man! Thank you for providing it for free!

[@SurajKumar-ex2kx]

Thank you so much sir. loving this series so much now Dp is my new crush due to you.

[@LuciferScripts]

lord of Dp. Thanks Bhaiya💙

[@harshchaudhary8182]

very underrated youtube channel, this is best u can get .

[@ashutoshdhyani8946]

Aditya...I had a query...cant we do this by same code as the equal partition sum....and at end traversing the T[0....n][sum] column and RETURNING NUMBER OF TRUE FOUND IN THAT COLUMN.....?..(btw loved ur videos

[@varunmahendra7772]

Thank you.. Thank you so much for standing by someone like me who is almost into depression just to understand these topics. That thank you id from bottom of my heart 🥺

[@umangjain3875]

Your explanation - awesome :) Thanks a lot bro. Never thought DP can be that easy :D

[@ameynaik2743]

Great video! Is there a leetcode problem based on this concept?

[@lifewithniharikaa]

Finally I reached a state at which I am able to do the question by my self.Thank youuu

[@DheerajGupta0651]

Congratulation brother on 100k subscribers you deserve millions of subscribers and one day you will achieve it.🎉🎉👏

[@TheAdityaVerma]

Thanks ❤️

[@lakshya8532]

Just a tip starts top-down dp loop, for J = 0 to sum+1, to handle If there is some 0 in the given array

[@thisthatvlogs5334]

And the best channel to learn dynamic programming

[@a.yashwanth]

I think there is no need. You can initialize dp[0][0]=1 and dp[0][1..sum]=0 Now you have only 1 row initialized. Now if you run the dp from i=1..n and j=*0*..sum If we run the j loop from 0..sum instead of 1..sum, it will count number of subsets for 0 too. If you still don't understand *how*: In first loop we are at _ element.(sum=0) 1 0 0 0 0 0 0 0 0 0 _ Now we apply the condition. if(0

[@sarthakbhatia7888]

doubt: in case when zeroes are present in the set given, the entries in the zeroth column may change for eg : arr[]={0,0,11,1}; then extra subsets for sum=0 {0},{0,0},{} so 1 will not work.

[@najimali32]

for each zero there will be two possibilities so count extra_zero & then add 2*extra_zero +t[n][W]

[@a.yashwanth]

​@@najimali32 I think there is no need. You can initialize dp[0][0]=1 and dp[0][1..sum]=0 Now you have only 1 row initialized. Now if you run the dp from i=1..n and j= *0* ..sum So we run the j loop from 0..sum instead of 1..sum, it will count number of subsets for 0 too. If you still don't understand *how* : In first loop we are at _ element.(sum=0) 1 0 0 0 0 0 0 0 0 0 _ Now we apply the condition. if(0

[@ankitsrivastava2929]

8:07 reduce playback speed to 0.75 and learn that too!!!!!

[@Akshitgupta1]

"Yaar aisi problems krne mai kitna maza aara hai!!", just awesome!

[@indianyatrivlogs]

Sir!please make videos on backtracking as well ❤

[@ketanraut9468]

Definitely the best dp explaination ever🔥👍

[@peoplechoice7848]

Bhai aapka knowledge toh kamaal ka hai bhai

[@namangupta8609]

bhai aap unsung hero ho placements ki duniya k

[@abhishekpaul8515]

100x better than any paid course 🔥

[@hemantmarve3674]

DP looks very easy after Learning from u.Thanks bro.

[@arpanbanejee5143]

Baki log sab matrix bharne lag jaate hain! Code karne aye ho matrix thodi na bharne aye ho! True AF!!

[@priyarathore9266]

Best DP course on internet!

[@onkarjoshi8811]

need more explanation on why used + did not understand the intuition behind it

[@codelover847]

Vai u're love. BitManipulation ka vi video banao.. Especially the approach needs to be understood and u're just nailing it.

[@TheAdityaVerma]

Thanks brother, next is binary search. I will consider making on Bit Manipulation. Thanks for the advice.

[@nemesisanims7401]

@@TheAdityaVerma Bhaii please yaar bass itna bata sakte ho aap ki minimum path sum kis type ka dynamic problem Qn hai ??? Please iska reply zaroor karna yaaran

[@lifeexplorer2965]

You Nailed it ,awesome

[@BHARATKUMAR-dk1ij]

you r a legend, yaar matlab extra dimmag lag hi nahi raha ,just normal changes and everything is explained properly

[@AnkitAsatiM10]

every time I watch your video, ek jaadu ki jhappi dene ka mann karta hai...😉😃😃❤️

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@ayushbansal9212]

Coding wale bnde hai ab baithke table thoda na bharenge!, Great video!

[@TheAdityaVerma]

Exactly brother !! ✌️

[@AnkitKumar-yj1sy]

Nice video 👌👍 awesome!!

[@ankitchouhan8828]

Great Video Brother. Keep Growing.

[@raviapiit]

"kya samjhate hain samjh nahi aata" :D Exactly, most of the time they fail to explain "why" ? instead directly start telling it's DP problem. But, first of all we need to understand why DP why not recursion or any other method. How would someone conclude that's DP problem (when looking at the similar problem in interview/exam). Most of the youtuber skip this part.

[@a.yashwanth]

especially tushar. tushar: see's a dp question also tushar: turns on camera and starts explaining the dp table immediately.

[@gautamvashishtha3923]

Bhaiya it would be awesome if you could do a similar series on Divide and Conquer based questions :) Thanks for the help

[@sumitbhuwalka]

@Aditya Verma Firstly the video and approach is very good. I tried this approach but it was failing for test cases containing multiple 0s such as: arr[]={0,0,1} sum=1 Expected Output: 4 My Output: 1 Maybe I missed something, can you suggest me something? P.S.: The testcase is present in leetcode targetsum problem as {0,0,0,0,0,0,0,0,1}, sum=1, correct ouput = 256, my output=1

[@BiharCentralSchool]

Start second loop from 0. int perfectSum(int arr[], int n, int sum) { int dp[n+1][sum+1]; for(int i=0;i

[@codetochange8]

@@BiharCentralSchool It helped a lot ...Thanks!

[@damnitboi4146]

Bro i donno hindi much still I am able to grasp stuff and this is legendary 🔥🔥🔥🔥🔥🔥

[@stayawakebrother]

impressed by the 8:08 pen trick

[@gauravbhisikar6381]

thank you bhai you explained 1000x better than my college teachers

[@niladribiswas1211]

After we generate the dp or t matrix , if we count number of true at last column we can get the number of subset. Can we say that?

[@vatsalagarwal8680]

If there is a number 0 in the array given initializatoin will be different for j = 0, as it will come 2 somewhere ?

[@paramgoswami7224]

See if there is 0 in the array, do the code for non zero elements.. And then multiply the answer by 2 as you will get one subset without taking 0 and other taking 0 both will give same results

[@a.yashwanth]

@@Astagfirullah.. There is code in this comment section.

[@a.yashwanth]

​ @NAJIM CHOUDHARY I think there is no need. You can initialize dp[0][0]=1 and dp[0][1..sum]=0 Now you have only 1 row initialized. Now if you run the dp from i=1..n and j= *0* ..sum So we run the j loop from 0..sum instead of 1..sum, it will count number of subsets for 0 too. If you still don't understand *how* : In first loop we are at _ element.(sum=0) 1 0 0 0 0 0 0 0 0 0 _ Now we apply the condition. if(0

[@harshittrehan6232]

@@a.yashwanth this is the more efficient approach. Thanks. I went with 2^num of 0's, but this is better.

[@A_CupOf_Life]

Amazing explanation brother. But Bhai same code nai chala, (in gfg), after searching here n there(took lot of time) found the reason.,(After Initialization , for loop (for sum) should start with 0, and not with 1). You could have mentioned this point as well in video.😊

[@mukulbakshi28]

Love you Bro, Ab lag rha hai ki koi Jada Smart ni hota all are equal its just concepts that you make very easy bro. One Feedback bro please also mention Space-Time Complexity analysis during Problems.

[@VinayakSrivastava101]

Wonderful explanation. Thanks