11 Count the number of subset with a given difference
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- Given an array Arr[] and a difference diff, find the number of subsets that array can be divided so that each the difference between the two subset is the given diff.
Example1:
Input:
Arr[] : 1,1,2,3
diff: 1
Output: 3 .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
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!
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;
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
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
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 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 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 are one of those unique content creators bro! Keep it up!
Thanks brother, Do subscribe and share, that keeps me motivated to do more !!
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!
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
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
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.
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.
So this playlist is DP in itself 🤩 .
underrated comment
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
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!!
I almost gave up coding until i found your Channel.
Thank you.
And yeah, i did not skip the add. 😀
your clarity of problem explanation is astounding.
If the differenec comes to be negative. For eg arr = {100} and d = -200. Fix: Just check if(diff>sum || diff
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!🙏🏻
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 .
last mei jo hamesha sum up karte ho vo bohot helpful hota hai..revise hojata hai.
💯💯
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?
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.
Didn't needed to watch it, with your previous classes solved it myself! Thanks, Sir.
You are a genius with amazing teaching skills, Keep up the good work. God bless you with more wisdom.
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 :)
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 +
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.
You are the hero of dynamic programming.
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
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
Your's Dynammic Programming Series and Striver's Graph series !! Lit !! Explanation k baad code dekhne ki hi zarurat nhi padti !
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
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 you, bro!! May God bless you... your way of teaching is too good man!!!
ADITYA VERMA || AMAZING TEACHER || PURA CONCEPT FAD KE RAKH DIYA || HATS OFF TO YOU DUDE
The way you explain your thought process is amazing 🙌🏻
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!
Best teaching method and best coding explanation yet.
dude you are pretty awesome with such a calm attitude and amazing explanation skills .
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).
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?
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
Bhaiiii,kya hi link kara hai is problem ko doosri problem se 🤯😊. Veryy nice 😍
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.
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🔥
Aditya bhai I am just freaked out!!!.. ye perspective to kabhi socha hi nahi tha
Gajjab sirji... Hatsoff
amazing:)), Seriously hope this channel grows by leaps and bounds.
Your explaination is out of world.
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???
(sum-diff)/2 also it will work , it will count the subset of lower side .... sum+diff/2 will count for higher side .... s1=4 , s2=3.... then sum+diff/2= 7+1/2==4 (higher side) when we do sum-diff/2 =3 (lower side ) ....... Both cases will work ....
Awesome man, You are too good in explaining DP problems in easy way. Waiting lectures on other concepts as well.
what a way of illustrating problem...best dp lectures .....ab dp fav topic bn rha hai mera
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
provide the question link in the Description. And keep doing the good work
You are an amazing teacher.. Hats off!!! Please upload more videos on different data structures.
Thanks.man ! Watched all ur previous videos..solved without even looking at this video.
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
amazing explanation in all your videos...dp seems easy after following your lectures
All the concepts are crystal clear ❤️
This whole BIG problem got deduced to just solving two simple linear equations! :/
kya yaar...itna simple tha :o
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 !!
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
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.
wow sir you are best teacher in this world
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.
can skip to 12:39 ,can uderstand easily with that part of video only.
Best DP course on internet!
yaar har viddeo me speechess ho jaa rha...kaha se kaha aaja rhe...best explanation
😂 Thanks brother, Do subscribe and share among your friends if you like the content.
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?
Sir, you are just amazing.
Real hero for us🙏🙇
You should have checked whether (totalSum + difference) %2 == 0 or not otherwise it will give worng answer
For e.g., if we have arr ={1,2} and I ask for no. of subsets who have difference = 2 then you would search for those subsets whose sum = (totalSum + diff)/2 = (3+2)/2 = 2 and will give 1 as answer because {2} is subset whose sum is 2 but the actual answer should be 0 because there are no two subsets whose difference is 2!
If someone says {2} and {} is possible then he is wrong because these subsets doesn't follow the given condition of totalSum=s1 +s2
We have totalSum = 3!
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👍🏻
❤️❤️ keep it up. The OP channel for competitive coding
Your teaching style is amazing bro 🔥🔥
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.
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 wish ki humare colleges bhi aise hi sikhate.
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 ?
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)
@@arijitsarkar1681 ok thanks 👍🏻
What explaination only because of u i am getting the concept.thank you🙏🙏🙏🙏🙏🙏
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.
what if subset (S1 U S2) != given array, like S1 = {2} , S2 = {1} still gives difference = 1. how to count all such possibilities also?
Great explanation. Can you help with a video on Partition to K equal subset sum problem
please make more videos on graphs!!!!! please !! these are so wonderful
Thanks you so much bro for these awesome videos . Your videos gives motivation to learn Algorithms . 🥰🥰🥰 Otherwise I always feel DSA very tough.
15:58 par thattt drawaing!!!! mashallah!!!!!
You're doing god's work.. Thank you
bhai god level teaching..thoda recursion v start kardo..maza ajayega❤❤❤
can someone share the problem link to this question .
i can't find it anywhere
thanks in advance
Same here dude. If u got pls mention here link..
Very nicely done please show us the approach to solve questions like "how many N digits numbers are possible such that their digitl sum is some K"
sir , your explanation is amazing.
This solution need some extra condition for getting answer here , many test case fail because we simply did it , need to know how
it is going on like a odd total can not be divided with even difference . and even sum can not be divided into a odd difference.
Amazing Work Bro :-). Thanks a lot, it is really helpful.
try nums=[2,3] and diff=2. solution should be 0, but output is 1. (basically any case with sum(nums)+diff being odd)