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
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!!!!
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 :)
You are the best DP teacher in TH-cam, 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!!!.
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.
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!
@@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
@@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
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
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
@@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
@@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
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.
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
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.
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.
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!!
@@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.
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
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.......
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
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 :)
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!
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.
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.
@@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 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.
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
@@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?
I Don't usually comment on TH-cam videos , but this playlist deserves a STANDING OVATION!! I repeat , This playlist deserves a STANDING OVATION!! Thank you so much .
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???
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
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.
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.
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.
SOLVED THIS ONE BY MYSELF I FEEL LIKE A GENIUS!! i mean not a biggie, especially after bhaiya's amazing explanation but i had just been struggling with dp so much.
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.
why are u destroying other TH-camrs 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
@@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
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.
It can also be seen as S2-S1=diff and S1+S2=Range. Therefore Range - 2S1 = diff. And S1 = (Range-diff)/2 . So instead of (sum+diff)/2 , we can use (Range-diff)/2 also.
@@AnubhavTalukdar true same. actually when i tried to solve this ques by myself at first, i came up with this and then i watched the video and saw he used the different one..... Anyways great and glad to know you thought the same👍🏻
If we know s1 - s2 and s1 + s2 then we can just take out s1 and just use the subset sum code , to get the count of the subsets that will have sum equals to s1.
Dude, you are freaking amazing!!! You're the best DP teacher on TH-cam. Kudos to you :)
Thanks! Also Check out my other playlist, Almost same as DP !!
@@TheAdityaVerma can you please provide practice link. It will be highly useful.
@@TheAdityaVerma 🔥🔥 bro you make my day man 🔥🔥🔥
kis company me ho dada
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
thanks helped :)
why %1000000007 is done?
@@gitansh2537 its also checking for extremely large data given in the problem
Thanks very much
why this ?if((diff+totalSum)%2 != 0) return 0;
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!!!!
those are just fancy lectures nothing is there in them
11 of 50 (22%) done! Very nice explanation. Repetition of concepts helps solidify the understanding.
This playlist deserves a STANDING OVATION!! Amazing!
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 :)
th-cam.com/video/j7NodO9HIbk/w-d-xo.html
You are the best DP teacher in TH-cam, 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!!!.
How did the interview go?
hey did you get selected?
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.
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!❤️
true bro
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!
Everyone was gagstar until the quiet kid open their youtube channel.
That kid had enough of the bullshit.
@@TheAdityaVerma LA LA LA...Snoop Dog..Thug Life...
@@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
@@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
@@MdKais-lf6wj if (sum[arr] + diff is odd) return 0;
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
problem link ?
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
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
I think this will not work if it contains duplicate elements
@@dotsol9200 can you please explain how it will not work.
@@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
@@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
This will work. I also did the same.
You are one of those unique content creators bro! Keep it up!
Thanks brother, Do subscribe and share, that keeps me motivated to do more !!
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
Exactly
I almost gave up coding until i found your Channel.
Thank you.
And yeah, i did not skip the add. 😀
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.
wrong answer a raha he
@@soumodeepmaity2810 absoulute value karni padegi
@@soumodeepmaity2810 can you send the link where you are practising this problem. I am not able to find one.
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.
@@JaspreetSingh-kp1zn Right, but when we try for this example, nums = [1,0] and diff = 1, it gives ans 1 instead of 2.
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
So this playlist is DP in itself 🤩 .
underrated comment
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.
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.
That's what I wast thinking as well🤔
It should be S1=(Sum-diff)/2. Is not it?
@@shivamdhaka8755 if we choose whole array as a single subset and other one is empty, then you will get other pair
@@hustler516 if u calculate S2 then you will get +
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!!
your clarity of problem explanation is astounding.
You are the hero of dynamic programming.
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.
Yes and if we don't return zero then we get a wrong answer in it .
Can you pls explain logic behind this? Why, if sum(arr)+diff is odd, there won't be any subset at all. Thanks
@@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.
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......
@@manishsharma-mt5jn arr=[1 1 2 3 7 10] , diff=5 .. solve for this. here summation is even and diff is odd
ADITYA VERMA || AMAZING TEACHER || PURA CONCEPT FAD KE RAKH DIYA || HATS OFF TO YOU DUDE
Didn't needed to watch it, with your previous classes solved it myself! Thanks, Sir.
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
thanks bro
Thanks a lot
This comment is a gem! Saved hours!🙏🏻
can skip to 12:39 ,can uderstand easily with that part of video only.
Best teaching method and best coding explanation yet.
last mei jo hamesha sum up karte ho vo bohot helpful hota hai..revise hojata hai.
💯💯
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.......
You are a genius with amazing teaching skills, Keep up the good work. God bless you with more wisdom.
Aditya bhai I am just freaked out!!!.. ye perspective to kabhi socha hi nahi tha
Gajjab sirji... Hatsoff
Your explaination is out of world.
Love you, bro!! May God bless you... your way of teaching is too good man!!!
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
@@KazHachiOreki just start second loop with j=0;j
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 :)
Your's Dynammic Programming Series and Striver's Graph series !! Lit !! Explanation k baad code dekhne ki hi zarurat nhi padti !
The way you explain your thought process is amazing 🙌🏻
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?
If the differenec comes to be negative. For eg arr = {100} and d = -200. Fix: Just check if(diff>sum || diff
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!
amazing:)), Seriously hope this channel grows by leaps and bounds.
wow sir you are best teacher in this world
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.
how will it reduce the size of array??
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.
@@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).
(sum_of_arr + diff) % 2 == 1 ) return 0;
why is the logic behind using this ?
@@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.
Bhaiiii,kya hi link kara hai is problem ko doosri problem se 🤯😊. Veryy nice 😍
dude you are pretty awesome with such a calm attitude and amazing explanation skills .
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
I am a little late to the party but would like to reiterate, you are good man...really good!
I appreciate that! :D
@@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?
All the concepts are crystal clear ❤️
I Don't usually comment on TH-cam videos , but this playlist deserves a STANDING OVATION!!
I repeat , This playlist deserves a STANDING OVATION!!
Thank you so much .
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.
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???
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).
what a way of illustrating problem...best dp lectures .....ab dp fav topic bn rha hai mera
Thanks.man ! Watched all ur previous videos..solved without even looking at this video.
You're doing god's work.. Thank you
kya he padha rhe ho bhai..
ek no
No one can teach like this.
Bhai tu bahut tagda padhata hai. And thanks for this series.
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
No words just wanna thank you for all your efforts!!
Isska ques link koun sa h bhai??? Nhi mil Raha mujhe
@@whatsnext7778 Ha bhai nhi mila , mila hoga to share kardo
Your teaching style is amazing bro 🔥🔥
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.
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🔥
We should also check if the (difference+sum(array)) is odd.
In that case, there will be no subset present with the given difference.
ha sahu he
provide the question link in the Description. And keep doing the good work
again no words for appreciation !!
No need for appreciation brother just share the content in your college and among your friends and help this channel grow !!
daaaammmnnnnn!!!!!!!!!! This is so good 7:09 🤯🤯
Best DP course on internet!
Awesome man, You are too good in explaining DP problems in easy way. Waiting lectures on other concepts as well.
Sir, you are just amazing.
Real hero for us🙏🙇
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.
sir , your explanation is amazing.
I wish ki humare colleges bhi aise hi sikhate.
❤️❤️ keep it up. The OP channel for competitive coding
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.
This whole BIG problem got deduced to just solving two simple linear equations! :/
kya yaar...itna simple tha :o
Hats off Aditya sir..Best dp teacher in TH-cam.
SOLVED THIS ONE BY MYSELF I FEEL LIKE A GENIUS!!
i mean not a biggie, especially after bhaiya's amazing explanation but i had just been struggling with dp so much.
bhai bhai, you are amazing, thanks for teaching on yt❤
can you provide the link of the Q?
amazing explanation in all your videos...dp seems easy after following your lectures
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.
You are an amazing teacher.. Hats off!!! Please upload more videos on different data structures.
Bhaiya iska source question mill sakta hai kya?
Apne iska description mei bhi kuch nahi diya
why are u destroying other TH-camrs 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
Bole to great explanation ❣️
Great work man, you are a great teacher.
Bhaiya, sumofarray+difference = odd bhi to ho sakta hai, tab apan directly return karenge na?
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
@@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
@@SuryanshsVerma how ??
Take the same example in video just change diff = 2 then 2(s1)=9
what if subset (S1 U S2) != given array, like S1 = {2} , S2 = {1} still gives difference = 1. how to count all such possibilities also?
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.
GREAT LECTURES,
love from NIT allahabad!
Can anyone share the problem link for this question?
Brother you are on another level🙏
Thanks brother, Do subscribe and share, that keeps me motivated to do more !!
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
Could anyone share the problem link please?
It can also be seen as S2-S1=diff and S1+S2=Range. Therefore Range - 2S1 = diff. And S1 = (Range-diff)/2 . So instead of (sum+diff)/2 , we can use (Range-diff)/2 also.
Is it giving the correct output when used count of subset sum is done on (Range-diff)/2?
@@AnubhavTalukdar yes its giving the right output 👍🏻
@@nitinbisht8575 Great! Even I thought why don't I just use the formula from the previous question instead of having to memorize a new one!
@@AnubhavTalukdar true same. actually when i tried to solve this ques by myself at first, i came up with this and then i watched the video and saw he used the different one..... Anyways great and glad to know you thought the same👍🏻
If we know s1 - s2 and s1 + s2 then we can just take out s1 and just use the subset sum code , to get the count of the subsets that will have sum equals to s1.
pls provide link to the question