11 Count the number of subset with a given difference

[@abhikbhattacharya1130]

Dude, you are freaking amazing!!! You're the best DP teacher on KZbin. Kudos to you :)

[@TheAdityaVerma]

Thanks! Also Check out my other playlist, Almost same as DP !!

[@rahulanand3099]

​@@TheAdityaVerma can you please provide practice link. It will be highly useful.

[@icecut7403]

@@TheAdityaVerma 🔥🔥 bro you make my day man 🔥🔥🔥

[@ankit_yadav11]

kis company me ho dada

[@0anant0]

11 of 50 (22%) done! Very nice explanation. Repetition of concepts helps solidify the understanding.

[@akarshansrivastava9379]

Your lectures are addictive I am watching 6-7 lecs per day for last 3 days . Didn't get this level of confidence even after watching MIT-OCW lectures . You're Just Amazing!!!!

[@TuringTested01]

those are just fancy lectures nothing is there in them

[@harshitasingh963]

This playlist deserves a STANDING OVATION!! Amazing!

[@viveksuman9600]

TWO REASONS FOR NOT GETTING ACCEPTED: 1) We are initialising first column to 1, assuming there is only 1 way to make subset sum equal to 0, i.e. null subset, BUT this fails if we have 0's as elements of array. If we have a single 0 present in the array, then the subsets will be '{}, {0}' whose sum will be 0. Hence, there can be more than 1 way to make sum==0. FIX: Don't initialise the first col to be 1. Everything will be initialized to 0 except the first cell in the table i.e. dp[0][0]=1. AND j will start from 0 instead of 1. 2) We also need to take care of the edge case where it's not possible to partition the array. In the derived formula, target = (diff+totalSum) / 2, NOTICE that (diff+totalSum) must be even for target to be a whole number, else it's not possible to find a decimal target in subset sum. FIX: Check, if it's odd, there is no way --> if((diff+totalSum)%2 != 0) return 0; ACCEPTED CODE C++: int countPartitions(int n, int d, vector& arr) { int sum=0; for(auto i: arr) sum+=i; if((d+sum)%2 != 0) return 0; int t=(d+sum)/2; //REDUCED: find count of subset with sum equal to t vector dp(n+1, vector(t+1, 0)); dp[0][0] = 1; for(int i=1; i

[@jigyasakodnani]

thanks helped :)

[@gitansh2537]

why %1000000007 is done?

[@RohitSharma-un2ir]

@@gitansh2537 its also checking for extremely large data given in the problem

[@nsmworldentertainment4687]

Thanks very much

[@raginibhadani7257]

why this ?if((diff+totalSum)%2 != 0) return 0;

[@a-064ramakantchhangani4]

He explains the concept in deep and then sum it up like a pro. That is what I like the most about this guy. Many youtubers start with a passion and in the end just show the output 'ya its running' with actual numerical examples which generally confuses people. Keep it up sir! Binary search playlist is next :)

[@Ayush-lj6pq]

kzbin.info/www/bejne/oGixoJeFbq18mM0

[@lifeofbalaji]

You are the best DP teacher in KZbin, period!. I spent days wondering how to start learning DP for my amazon interview prep. The fun part is I don't even know that much Hindi but just the way you display your intuition helps me. Thanks for taking your time out in preparing these videos. You deserve more subscribers man!!!.

[@raunak1786]

How did the interview go?

[@yadneshkhode3091]

hey did you get selected?

[@mridulkumar786]

I thought this one is the toughest among above all problems but the way you explained it really made this problem too easy to code now. Seems like one of our friends is teaching us just before exams.

[@sandravsnair5061]

Usually, I'm not a person who comments in youtube videos, but couldn't resist this one. My senior suggested this channel to me just yesterday. Great stuff for DP! I was really scared of this topic but I guess I will be able to perform well after watching the whole playlist. Awesome! Keep going!

[@AnkitAsatiM10]

you remind me of my study in hostel days when friends like you just made everything look so easy! Amazing! Lots of love and respect for you buddy!❤️

[@sharaj4893]

true bro

[@AbhishekKumar-qb3ls]

You have developed the concept in me through the previous problems in such a way that I solved this problem within two seconds Thanks Bro

[@anjaligarg498]

I can't believe i was able to solve this problem before i saw your solution. Thank you so much for teaching us the logic otherwise i used to get afraid after reading these kind of problems. Thank you so much :) . Keep up the good work

[@alok92066]

problem link ?

[@romiccomic9229]

I almost gave up coding until i found your Channel. Thank you. And yeah, i did not skip the add. 😀

[@arhamnaeem5820]

The fact that you amazingly relate one problem to the another is just mind blowing and so easy to understand! Thanks for these amazing videos

[@vishnusaitejanagabandi9009]

Exactly

[@rohitjaiswal4121]

You are one of those unique content creators bro! Keep it up!

[@TheAdityaVerma]

Thanks brother, Do subscribe and share, that keeps me motivated to do more !!

[@tanmoychowdhury5666]

At last got some real stuff to digest. Thank you Aditya. By the way, What about, if we try to count unique subset combination for given difference?

[@KlassiKale]

Thank you for your videos on DP. And now that you have recently switched to paperless medium, you owe your readership a video just of your pen flipping tricks :) . Thank you again!!

[@mohann4884]

you can improve the performance by this "sum-difference/2" instead of "sum+difference/2". So in this case you will calculate the count of subset sum for a smaller number sum.

[@soumodeepmaity2810]

wrong answer a raha he

[@dev_among_men]

@@soumodeepmaity2810 absoulute value karni padegi

[@shreyajindal4685]

@@soumodeepmaity2810 can you send the link where you are practising this problem. I am not able to find one.

[@JaspreetSingh-kp1zn]

Yes, instead of adding 2 equations , we could try subtracting ii) from i) equation in video then we would get s2 = (sum(Arr)-diff)/2.

[@anandpol3650]

@@JaspreetSingh-kp1zn Right, but when we try for this example, nums = [1,0] and diff = 1, it gives ans 1 instead of 2.

[@HimanshuKumar-xz5tk]

This can also be solved like this-> S = sum of array S1 = sum of first subset S2 = sum of second subset S2 = S-S1 so, S2-S1 = (S-S1) - S1 = S-2*S1 This value should be equal to diff We know every possible value of S1 will exist in last row of dp[n+1][sum+1] So just count number of values for which dp[n][j] = true and S-2*j = difference

[@dotsol9200]

I think this will not work if it contains duplicate elements

[@manishkumarparmar412]

@@dotsol9200 can you please explain how it will not work.

[@shivam7304]

@@manishkumarparmar412in this approach we are actually finding through sum , which is not distinct for 1,2 or 2,1 (both of whose sum is 3) while in the case shown by aditya different elements can be there

[@dotsol9200]

@@shivam7304 Exactly shivam . I thought I was alone and everybody is commenting that this idea would work but it is not true. It is only for distinct elements not for duplicate elements

[@prakashgatiyala9869]

This will work. I also did the same.

[@AbhijeetMishra-bl7yr]

your clarity of problem explanation is astounding.

[@human75788]

Didn't needed to watch it, with your previous classes solved it myself! Thanks, Sir.

[@saikirananumalla4058]

So this playlist is DP in itself 🤩 .

[@sushmasingh317]

underrated comment

[@MrSatishkumarchakka]

You are a genius with amazing teaching skills, Keep up the good work. God bless you with more wisdom.

[@deepanshjohri3997]

Love your concept sir Just after problem statement I made this question myself #include using namespace std; int countsubsetsum(vector v,int sum) { int n=v.size(); int t[n+1][sum+1]; for(int i=0;i

[@rajatgupta8527]

@@KazHachiOreki just start second loop with j=0;j

[@shubhamprashar7676]

NOTE: You have to compute the number of pairs of such subsets whose difference == given target. If you find abs(currSet-(sumArr-currSet)) then you are not counting the pairs instead you are counting the individual subsets which will come out as 6 instead of 3.

[@shivamdhaka8755]

I have a similar type of situation, can u help me understand this: I have a question for all of you: can anyone tell me what should be the output of this array: [3,7,4] and the difference is 0; and what will be the output according to the taught formula i.e, sum+diff /2 = 7 ..... clearly, there is 2 subset with a given sum i.e, {7} and {3,4} but manually the output should be 1 as there is only 1 pair of subset which will give the asked difference i.e, {7} - {3,4}; If anyone could tell me then it will be a great help for me.

[@batmanarkhamcity3684]

That's what I wast thinking as well🤔

[@hustler516]

It should be S1=(Sum-diff)/2. Is not it?

[@khushichoudhary2133]

​@@shivamdhaka8755 if we choose whole array as a single subset and other one is empty, then you will get other pair

[@awesome_latest_virals6098]

@@hustler516 if u calculate S2 then you will get +

[@nitikagupta159]

Best teaching method and best coding explanation yet.

[@manishmotwani3744]

Thanks Aditya sir for making such a wonderful DP series for free!! Your way of explaining the concepts is amazing.. This series helped me a lot to understand DP cleary :)

[@somyacharanpahadi1221]

one of the best videos finally i am enjoying coding and its all because of you and my friend aditya who suggested your playlist for DP. Thanku soo much.......

[@prachij]

The way you explain your thought process is amazing 🙌🏻

[@thisthatgirl5060]

You are the hero of dynamic programming.

[@spideranup]

ADITYA VERMA || AMAZING TEACHER || PURA CONCEPT FAD KE RAKH DIYA || HATS OFF TO YOU DUDE

[@tusharjolly2734]

Love you, bro!! May God bless you... your way of teaching is too good man!!!

[@techcheatsheettutorial129]

Your explaination is out of world.

[@ankitsablok952]

Bhaiii! Ye Videos Ko CS Museum main de dena chahiye! These are treasure, pure fucking Gold! The explanation style is just magical and magical with "M". God bless you bro! Such an amazing Content and such an intelligent way of getting people to develop their minds for DP. Really Amazing!

[@mkmohitkmr]

When sum(arr) + diff is an odd number, then there won't exist any subset like that and we can return zero from there itself.

[@jaydalsaniya6986]

Yes and if we don't return zero then we get a wrong answer in it .

[@AdpYTExplorer]

Can you pls explain logic behind this? Why, if sum(arr)+diff is odd, there won't be any subset at all. Thanks

[@VirajChokhany]

@@AdpYTExplorer if sum(arr)+diff is odd, then the sum of subset s1 will be odd/2. say if sum(arr)+diff is 9 , then sum of s1 should be 4.5. You can not get a sum of 4.5 (float) in an array of integers. If you pass it to function, it will truncate 4.5 to 4 and there may be a subset whose sum might be equal to 4 and hence a wrong answer.

[@manishsharma-mt5jn]

in this question every time we will get ..diff and sum both as odd or both as even ......ans summation of two odds or 2 evens always gives even......

[@HimanshuKumar-rn1cn]

@@manishsharma-mt5jn ​ arr=[1 1 2 3 7 10] , diff=5 .. solve for this. here summation is even and diff is odd

[@deepaksuthar5703]

if diff+sum(arr) is odd then we get wrong Output example :- arr[] = 1,3,5 diff = 2 then sum(arr)+diff = 11 sum(s1) = 11/2 = 5 your code output will be = 1 right output is 0 we can write one line that if diff+sum(arr) is odd then output will be zero. thanks for your videos

[@कत्यूषा]

Everyone was gagstar until the quiet kid open their youtube channel.

[@TheAdityaVerma]

That kid had enough of the bullshit.

[@yashveernathawat8154]

@@TheAdityaVerma LA LA LA...Snoop Dog..Thug Life...

[@MdKais-lf6wj]

@@TheAdityaVerma one question: if the (sum[arr]+diff) is odd! then we divide it by two.then the number becomes float first then the number becomes less than or greater than by one.then what can we do? what is then it's output. plz help me

[@SaurabhSingh-sm2mt]

@@MdKais-lf6wj return zero if the sum(arr) +diff is odd because in that case you can't have a subarray with the required sum *given array contains only positive integer

[@rishabhranjan2122]

@@MdKais-lf6wj if (sum[arr] + diff is odd) return 0;

[@jitendraraghuwanshi8635]

if you're afraid of a little math this modified snippet from subset sum with minimum difference will also work :- basically what I am doing is returning the count of subsets with difference =diff. for (int i = 0; i

[@jayantakumarroy543]

last mei jo hamesha sum up karte ho vo bohot helpful hota hai..revise hojata hai.

[@agyaani8060]

💯💯

[@ShivamDubeymike]

Aditya bhai I am just freaked out!!!.. ye perspective to kabhi socha hi nahi tha Gajjab sirji... Hatsoff

[@RaviYadav-dz3ir]

Your's Dynammic Programming Series and Striver's Graph series !! Lit !! Explanation k baad code dekhne ki hi zarurat nhi padti !

[@Birendrakumar-sf5kd]

Hi Aditya, I really enjoying your video and you explained it beautifully. I want to add one thing in this video. Please mention Note: All the array elements need to be involved in generating the diff.

[@mayankgupta8474]

Great series of DP. I really like it, keep up the good work. In this problem we can add one check at the start if ( (sum_of_arr + diff) % 2 == 1 ) return 0; else find countOfSubSetSum() Also I like the suggestion to use (sum_of_arr - diff)/2 instead of (sum_of_arr + diff)/2 this will reduce the size of array.

[@sololearner7557]

how will it reduce the size of array??

[@vishal_rex]

Let's assume (diff+sum) is odd. To make it possible [diff,sum] must be either [odd,even] or [even,odd] Let's consider one case where sum is odd and diff is even. Or, s1+s2 is odd, so [s1,s2] = [even,odd] or [odd,even] But diff is even in this case. Or, s1-s2 is even. To make it possible, s1 & s2 both must be either odd or even. i.e [s1,s2] = [odd,odd] or [even,even] This is a contradiction my friend 😎 Hence (DIFF+SUM) IS ALWAYS EVEN.

[@vivekkumar-bq2ln]

@@vishal_rex stud Bhai, diff is an asked value, not a tested-asked (on the given set) value. Ur API user can anytime pass random diff value without even testing on it the set (that is the point of ur API as he doesn't know).

[@shibanidas7018]

(sum_of_arr + diff) % 2 == 1 ) return 0; why is the logic behind using this ?

[@MrUvwx]

@@shibanidas7018 if (sum_of_arr + diff) % 2 == 1 ) that means the sum of S1(subset 1) is having fraction part(53/2 = 26.5). But since all the elements of nums array are of integer type, sum of S1 must be an integer. which is not possible if the above condition is true.

[@vaishnavipampatwar6569]

dude you are pretty awesome with such a calm attitude and amazing explanation skills .

[@manav-chan]

Some test cases might not run, here's the solution for that, You can include a condition in main function that if sum of all array elements < difference, return 0. And before using the formula s1 = (diff+sum)/2, check if diff+sum is odd or not, in case it is an odd value then our s1 won't be a whole number, if odd return 0

[@ashishkumar-fg7ph]

thanks bro

[@asthaastha9041]

Thanks a lot

[@aishwaryshukla8880]

This comment is a gem! Saved hours!🙏🏻

[@parijatgarg3172]

amazing:)), Seriously hope this channel grows by leaps and bounds.

[@adityan5302]

I think this is the best video for beginners. I can be able to build the logic on my self. Great to have you bro... Hope you continue the playlist. Lot's of love from Hyderabad

[@Nikita-hv5jm]

thats so cool how by understanding the concept of just one problem all other tough problems became so easy...thanks a lot sir... hats off🔥

[@anuragnama5310]

Awesome man, You are too good in explaining DP problems in easy way. Waiting lectures on other concepts as well.

[@ppg3530]

can skip to 12:39 ,can uderstand easily with that part of video only.

[@Vishal-ds6ly]

wow sir you are best teacher in this world

[@cs04abhinavasthana36]

what a way of illustrating problem...best dp lectures .....ab dp fav topic bn rha hai mera

[@amanpandey2714]

Thanks.man ! Watched all ur previous videos..solved without even looking at this video.

[@DevrajSingh-wl9vw]

If the differenec comes to be negative. For eg arr = {100} and d = -200. Fix: Just check if(diff>sum || diff

[@anktrj]

provide the question link in the Description. And keep doing the good work

[@ankitdutta5240]

amazing explanation in all your videos...dp seems easy after following your lectures

[@riktamkundu3463]

In this example if we consider the internal subsets also then (1,2) will give us two more results for two different 1's and (2,3) will be another case...for bigger examples there might be more internal subsets like this which will yield our result...how to take them into consideration???

[@sumedharana4474]

You are an amazing teacher.. Hats off!!! Please upload more videos on different data structures.

[@pooja581]

Your teaching style is amazing bro 🔥🔥

[@prabhattiwari4125]

Bhaiiii,kya hi link kara hai is problem ko doosri problem se 🤯😊. Veryy nice 😍

[@varunsaini246]

Bhai tu bahut tagda padhata hai. And thanks for this series.

[@shapethetechworld]

I was able to write initial equations using previous problem analysis before watching this video. Wow, I'm learning DP now instead of remembering. Thanks, man.

[@rishikeshkumarsingh3283]

kya he padha rhe ho bhai.. ek no No one can teach like this.

[@subhadeepchakraborty2141]

All the concepts are crystal clear ❤️

[@priyarathore9266]

Best DP course on internet!

[@bhavyapandey7404]

Bhaiya, sumofarray+difference = odd bhi to ho sakta hai, tab apan directly return karenge na?

[@SuryanshsVerma]

2(sum(s1)=diff+sum(arr)------------>means rhs is even as lhs is given 2*sum of s1 which always be equal to even hence odd doesnt exist

[@sayantangupta6211]

@@SuryanshsVerma suppose arr = [1] and given diff = 2, then sum(arr) + diff = 1 + 2 = 3, which is odd. Thus odd might exist. In this case, I think if sum(arr) + diff is odd, return 0 as no subsets can be formed with given diff

[@veenitkumar4094]

@@SuryanshsVerma how ?? Take the same example in video just change diff = 2 then 2(s1)=9

[@gurulinggbiradar6982]

one minor optimisation instead of using s1 sum as it is bigger than S2 . Use S2= (sum - diff)/2 . this will reduce some space complexity.

[@prabhavdogra6567]

You're doing god's work.. Thank you

[@aryanchauhan8897]

I think there is a mistake in the above approach. E.g. if arr = 1,2,3,4 and diff = 1 then ans should be 0 but acc to above approach ans comes out to be 2. Acc. to above approach sum = 10, diff = 1 then val = (sum + diff) / 2 = (10 + 1) / 2 = 5. and there are 2 subsets with sum equals 5 is present in the array (2,3 & 1,4) thats why it is given ans = 2 but correct ans should be zero. So, correct approach should be when val is odd then ans is zero other wise ans is same as above approach. Correct me if I am wrong.

[@anjalirana4677]

daaaammmnnnnn!!!!!!!!!! This is so good 7:09 🤯🤯

[@jinnendrabaid1638]

sir , your explanation is amazing.

[@kushagragupta7234]

Sir, you are just amazing. Real hero for us🙏🙇

[@shashikantkumar5095]

why are u destroying other KZbinrs channels like that? How can you make problems so simple? It was the greatest decision of my life to click on this video. Ready to watch all our videos. Thanks

[@prashantsingh1621]

14:38 we should check (diff + sum_of_array) to be even before calling?

[@shashishekhar1729]

yup ,because the resultant sum has to distribute equally in order to make sure the two subsets have the given difference.

[@Tony-h6i]

I have done this one without going into the video You are really amazing...! I really want to meet you in person and thank you! I would wish there would be no hustles in your journey.

[@sohinidey6711]

Hats off Aditya sir..Best dp teacher in KZbin.

[@souravroy4701]

bhai god level teaching..thoda recursion v start kardo..maza ajayega❤❤❤

[@samirjha6101]

We should also check if the (difference+sum(array)) is odd. In that case, there will be no subset present with the given difference.

[@harshil1466]

ha sahu he

[@vivekupadhyay737]

Great work man, you are a great teacher.

[@Abhishekkumar-ek4kn]

Hey Aditya! First of all many many thank you on posting such an amazing content. I have a doubt this logic works only when S1 U S2 = whole array . what if they S1 U S2 is just another subset of array? In that case sum of S1 and S2 will not be equal to sum of all element s of array. A little more help by replying this comment would be appreciated. Thank you!

[@SreekantShenoy]

Yep, the question is framed like that.

[@arshgupta2891]

Thanks for giving me a new challenge , i will think about that.

[@trisha4985]

Same confusion

[@luvvermani1240]

Yes you are correct, the title is wrongly worded, I have also made a comment which asks and proves the same. S1 U S2 does not have to be S for the given title, it will be only true for the question, count of ways to partition array into two subsets with given difference. The current title would be a more general and harder problem.

[@sunnykumarjha9527]

yes same doubt🥲🥲

[@yashbudukh340]

Hii Aditya great playlist. I have a small doubt in this problem why are we assuming sum(s1) + sum(s2) = sum(arr) . For e.g arr= [1,2,7,1] and diff =1 Cant s1 and s2 be {1} and {2} resp. ?

[@ankitsharma8078]

bro 7 and 1 kaha gaye fir xD

[@GeetThaker]

looks like all elements must be used.

[@codewithrebel1286]

I don't know how but my understandig level of DP suddnely increased with this pen paper style or this is the magic of teaching style (Definitely).

[@joshijai2]

❤️❤️ keep it up. The OP channel for competitive coding

[@lifeexplorer2965]

again no words for appreciation !!

[@TheAdityaVerma]

No need for appreciation brother just share the content in your college and among your friends and help this channel grow !!

[@tanujgyan787]

I am a little late to the party but would like to reiterate, you are good man...really good!

[@TheAdityaVerma]

I appreciate that! :D

[@abhinavmenon3693]

@@TheAdityaVerma Hey Aditya, thanks for the videos! I have doubt, what about the condition where sumofarray+difference is an odd number? How will we find sum of subset 1 in that case? Will the answer by default be 0?

[@harshsahu7825]

Nicely done, again!

[@divyasimhadri4677]

I Don't usually comment on KZbin videos , but this playlist deserves a STANDING OVATION!! I repeat , This playlist deserves a STANDING OVATION!! Thank you so much .

[@shibangibarua2285]

please make more videos on graphs!!!!! please !! these are so wonderful

[@lifecodesher5818]

15:58 par thattt drawaing!!!! mashallah!!!!!

[@gauravnarang9954]

Great explanation. Can you help with a video on Partition to K equal subset sum problem

[@gaganjakhu714]

Output should be 5 Subsets another two subjects are whose diff. Is one :- 1.) {2} {3} 2.) {1} {2} Please correct me if I'm wrong ?

[@arijitsarkar1681]

You have to consider all the elements from the array. if you are choosing only two elements{2,3}then {1,1} are left .so you have to consider them also. Three pairs of subsets: 1.[1, 1, 2] and[3] 2.[1, 2] and[1, 3] 3.[1, 3] and[1, 2] (Because there are two 1's, so repitition of pairs is there)

[@gaganjakhu714]

@@arijitsarkar1681 ok thanks 👍🏻

[@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.

[@explorewithSomya_9]

This whole BIG problem got deduced to just solving two simple linear equations! :/ kya yaar...itna simple tha :o

[@ratishjain2718]

No words just wanna thank you for all your efforts!!

[@whatsnext7778]

Isska ques link koun sa h bhai??? Nhi mil Raha mujhe

[@Rajesh-op8zx]

@@whatsnext7778 Ha bhai nhi mila , mila hoga to share kardo

[@sujeetkumar.]

You are an awesome teacher.

[@ashvinimeshram5242]

What explaination only because of u i am getting the concept.thank you🙏🙏🙏🙏🙏🙏

[@ajeetpatel7991]

bhai bhai, you are amazing, thanks for teaching on yt❤

[@nikhilanand984]

Bhai you just made dp look like simple maths!! waiting for you to explain other topics and guide us in the journey of becoming sde!

[@nileshkhimani9315]

sir let's say n = 9 and given array : [ 0 0 0 0 0 0 0 0 1] and sum we want to get is : 1 what should we do in this case?

[@_AmbujJaiswal]

YOU ARE THE GREATEST OF ALL TIME SIRRRRR STILL ITS THE THE THE FUCKING BEST DP SERIES IN 2023 AND EVERRRRR THANKYOU SO MUCH SIRRR L0TS OF LOVE