DP 18. Count Partitions With Given Difference | Dp on Subsequences

a

In this video, we solve the problem of count partitions with given difference. This problem is the fifth problem on DP on Subsequences Pattern. Please watch DP 17 before watching this.

[takeUforward]

I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.

Keeping a like target of 500 ❤✌🏼

[AbhishekKumar-cvdh]

I'll be honest, I was bamboozled with the 0's in array edge case since DP17 and I was simply unable to find a clear answer from the comments. Had I simply closed my eyes and went ahead with DP 18, I would have legit saved ~ 2 hours of confusion!!
Thankyou so much Striver, this lecture cleared all my doubts 🔥🔥🔥🔥🔥

[saketsoni]

I studied DP from aditya verma, but was never able to figure out how to handle the zeros in the array, you made it super easy, Thanks!

[nikhilmadaan]

hats off man, , spent 2 hours on DP17 to fix that but after watching this DP 18 everything went super smooth

[PIYUSH]

The deduction of (totalSum - D) / 2 was amazing. Understood!

[saurabhsaha]

Striver's concept explanation is so cool, easy and easily get stuck into the head. I wish to meet him one day and say a lot of thanks to him.

[csdivyanshisachan]

Understood! Hats off to ur dedication, u are still teaching while suffering from fever.

[pulkitchausali]

Already understood before starting of video that's what Striver teaches us

[chetanthakral]

Another modified target could be (difference + totalSum)/2;
To explain this how this came is :
s1= sum of elements in subset 1
s2 = sum of elements in subset 2
s1 - s2 = d (We need to find 2 subsets with difference d )
s1 + s2 = totalSum (We know the sum of 2 subsets would be equal to the total sum of array)

Adding these 2 equations, we get s1 = (d + totalSum)/2, thus we only need to find a subset with sum s1.

[Aniruddha_Chowdhury]

understood until 14:00 ❤ .
Will learn the optimization later

[balajisrinivasan]

Thank you striver ! Just a note : writing recursion from 0 to n-1 looks far easier to handle bases cases than writing recursion from n-1 to 0 on subsequence problems

[narendramaurya]

Us, but the way you transformed the problem into previously solved problem is amazing, that's the way we have to think ... Thanks ❤

[blackblood]

we can also use :
if(ind < 0){
if(sum==0) return 1;
return 0;
}
apart from these conditions:
if(ind == 0) {
if(sum==0 || num==arr[0]) return 1;
if(sum==0 && arr[0]==0) return 2;
return 0;
}

[ankanbasu]

4:48 or I think, we can go 1 step deeer into indx = -1
then base case would be simpler

if (indx == -1) {
if (sum == 0) return 1;
else return 0;
}

[ScienceSeekho]

understood. Also thanks for explaining Space Optimization so good. I am from tier-3 mechanical never knew all these stuff

[adebisisheriff]

Understood! Striver. The best Software Engineer himself

[soumik]

solved this problem on my own very proud of this

[itsmepratham]

For Those who did not understand why total sum-d has to be even so imagine totalsum=15 and d=2 now count s2=(15-2)/2 it will give s2=6; ans s1-s2=d so s1=2+6=8 now here it is said that s1+s2=totalsum but s1+s2=14 which is not equal to total sum to total sum-d has to be even

[tarunrao]

Hello,
The tabulation code is not passing all test cases in both videos dp-17 && dp-18. Is anyone facing the same problem. Pls HELP.

[Lyrics_dunya]

For Problem 17, I struggled a bit in Tabulation while writing the base cases for the new changes.
All 3 cases covered, also notice the bases cases are written in reverse order, so that the priority is given to the last one if its true.
One more thing since we are considering the case for i = 0, please start the 2nd loop of target from 0 till k(inclusive). Happy learning!

dp[0][0] = 1
if arr[0] <= k:
if arr[0] == 0:
dp[0][arr[0]] = 2
else:
dp[0][arr[0]] = 1