11 Count the number of subset with a given difference

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:

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.

[abhikbhattacharya]

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

[akarshansrivastava]

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!!!!

[anant]

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

[harshitasingh]

This playlist deserves a STANDING OVATION!! Amazing!

[viveksuman]

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<int>& 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<vector<int>> dp(n+1, vector<int>(t+1, 0));
dp[0][0] = 1;
for(int i=1; i<n+1; i++) {
for(int j=0; j<t+1; j++) {
if(arr[i-1] <= j)
dp[i][j] = (dp[i-1][j] +
else
dp[i][j] = dp[i-1][j];
}
}
return dp[n][t];
}

[a-ramakantchhangani]

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 :)

[lifeofbalaji]

You are the best DP teacher in YouTube, 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!!!.

[AnkitAsatiM]

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!❤️

[mridulkumar]

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.

[AbhishekKumar-qbls]

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

[anjaligarg]

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

[sandravsnair]

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!

[romiccomic]

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

[mohann]

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.

[arhamnaeem]

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

[rohitjaiswal]

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

[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!!

[HimanshuKumar-xztk]

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

[AbhijeetMishra-blyr]

your clarity of problem explanation is astounding.

[shubhamprashar]

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.