10 Minimum Subset Sum Difference

[@LegitGamer2345]

note : you may not be able to do this using memoization since all values of lookup table are not filled in memoization , so do this using tabulation since tabulation guarantees that all values of dp table are filled

[@rohitarora8516]

yeah man found that after an hour of debugging :(

[@yath3681]

This comment should have more likes

[@kaushiksai1201]

you mean should we use the iterative approach and not the recursive approach?

[@rishigupta9680]

i done this problem by memoization

[@rikeshtrieseverything]

Here you go recursion with memoization code ---> class Solution{ public: int minDiff(int arr[], int n, int lsum, int rsum, vector & dp){ if(n==0) return abs(lsum - rsum); if(dp[n][lsum]!=-1) return dp[n][lsum]; return dp[n][lsum] = min(minDiff(arr, n-1, lsum-arr[n-1], rsum+arr[n-1],dp), minDiff(arr, n-1, lsum, rsum, dp)); } int minDifference(int arr[], int n) { // Your code goes here int sum = 0; for(int i=0; i

[@arjunreddy3615]

Interconnection between the questions is the best part in these tutorials... 😊

[@PoojaGupta-ry3oj]

Seriously I have seen lot of other programming channels on KZbin.. No one taught the way you did.. Connecting everything..No one can even reach ur level.. Best channel i would say.. Keep uploading.. Waiting for ur recursion and backtracking series.

[@rahulchauhan144]

Their are 2 types of Teachers : 1. Who Write code and then explain you 2. Who explain you and then write the code.... The difference is 1st one indirectly wants you to remember the code and 2nd wants you to Develop logic because if u know the logic u can write the code on your own that makes you an independent Guy. Aditya Verma is the 2nd one !! :)))) Nice work...Nice Way of teaching !!

[@ak67373]

Today , i realized views can't decide the level of the videos...

[@TheAdityaVerma]

Thanks brother, Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️

[@ankuragarwal4014]

@@TheAdityaVerma please do it asap please

[@abhishekbasu4911]

@@TheAdityaVerma Can you please include the explanation of Tree and Graph related concepts too when you get time in the month of May? :)

[@fadiahetrakeshkumar9454]

yes we want videos on graph

[@SHUBHAMSHARMA-cq7ob]

@@TheAdityaVerma bhai may aa gaya, graph aur tree ke videos kab aayenge bhai??

[@anshumansrivastava8108]

Thank you very much, Sir, this Q was asked in my Microsft Interview and I was successfully able to clear it .. because I had watched this video once. Thank you again and you're videos are very helpful and awesome.

[@Shourya_performs]

really? awesome man

[@ashutoshkumarsrivastava6331]

If we can think this, means the trainer is excellent.

[@DivyaNethri2310]

hi

[@Adonis08]

😯WOW

[@sahilreddy2080]

referral dede bro

[@himanshusoni1512]

Used in LC 1049. Last Stone Weight II Note to myself: You can start looping over last row dp matrix from range/2 to 0 and choose the first TRUE and BREAK, as first closest sum from the center would be the required sum.

[@mani_tyagi10]

clever approach bro

[@insaneclutchesyt948]

even i thought the exact same thing !

[@hawkeye_OG]

​@@insaneclutchesyt948or do half sum and run on sum/2 , the max value of last index at dp will be the max value possible but less than (if odd) or equal (if even) to the sum/2 , and get the last dp value , do absolute of sum-dpval*2

[@academywise]

Actually i am confuse in the subset function, we should make all dp table as true or false, and what we need to return, can you please help me.? public static boolean subset_sum(int[] arr, int sum, int size) { // Table initilization boolean t[][]= new boolean[size+1][sum+1]; for(int i=0;i

[@Spidywebb]

TRY this Leetcode - 2035 (Hard) Acceptance Rate - 19.9%

[@accesstosuccesshrsolutions5719]

I can say without a doubt that "Aditya Verma is god of DP" 😜. Great Work man!

[@nareshupadhyay1192]

Yes he is

[@0anant0]

At least make the 'g' capital! :-)

[@0anant0]

@@Harish-fx2mo Haha! Similar thing happened with me -- I used "He" (H capital) somewhere in the middle of a sentence and I was rudely reminded that "He" was reserved only for God! :-)

[@zarc5744]

You probably don't know about red coders then

[@vaibhavtiwari6992]

@@zarc5744 it's about the communication.

[@introvertsinger710]

We can actually reduce the space complexity by half... One observation is: Since only half of the last line is what we need, we can omit the right half of the matrix. i.e. we can create matrix of size something like.. t[ n+1 ][ ceil(sum/2) ]. And yes I have checked this approach, it works fine. In this you just need to check the last true in the last row of t matrix. and then desired output is total_sum - 2*(col_num_of_last_true). In this way, we can further reduce complexity( both time and space ) by not creating unnecessary vectors. I know ADITYA SIR knows this, he just told you in a way, which a newbie can also understand :)

[@yogesh970]

You can optimize like this for sure. But time complexity will still be the same..in Big O notation ...forget about constant part n = n /2

[@introvertsinger710]

@@yogesh970 obviously

[@amansinghgautam9578]

i am thinking the same.. thanks for the confirmation

[@amansinghgautam9578]

@@yogesh970 can you please explain why time complexity will not decrease

[@sudeepsrivastava4768]

@@amansinghgautam9578 because constant multiples don't effect the time complexity on a very big scale

[@VikashKumar-xr6fl]

At 40:23 do we need to iterate throughout the vector? Just substracting it twice of last element of the vector can give the minimum, as created vector will hold the maximum value at the last index and to minimize, we should substract maximum from the range

[@sanjayvasnani988]

Yeah you're right

[@madhavbudhiraja5421]

I came to comment the same dude 😂😂😂 @Aditya Verma should pin this.

[@mihirdesai1083]

Hands down these are the best tutorials for Data Structures and Algorithms out here! This guy helps build up the intuition and concepts like no one else.

[@satya_k]

Here is the C++ tabulation code with comments which works perfectly fine: int minDifference(int arr[], int n) { int sum = 0; for(int i = 0; i

[@malkeetsapien4852]

Arigato !

[@shivanshyadu4830]

thankyou so much buddy for sharing the code , i was getting some errors.

[@sohiltr2310]

thanks buddy :)

[@bubbit]

arigato

[@its_adit]

its not working on leetcode

[@mridulkumar786]

Last part could be solved efficiently: - int size=v.size(); // v is the vector as mentioned in video cout

[@AmandeepSingh-ot6st]

How would you store the last row from table to a vector .....

[@mridulkumar786]

@@AmandeepSingh-ot6st as mentioned in video

[@g10_de_coder]

I thought same bro 🙄

[@Sauravgpt34]

Yeah you're right return range - 2*vector[vector.size()-1];

[@TheIndianGam3r]

Won't make a difference on the overall complexity so its fine man. This way it is easier to understand for all.

[@anik._.]

I really appreciate your work and like your way of explaining this approach. I will just be commenting another approach of doing it using memoization. Intuition: 1. sum -> sum of all integers in the array 2. partitonOneSum -> the maximum possible sum which is less than or equal to (

[@praneethkaturi9321]

While using the bottom up approach(Tabulation) isn't it enough to construct the boolean table until (sum/2 ) instead of constructing the table until (sum)? In the end all we care about is the value closest to (sum/2) right?

[@manavmohata1240]

You're right

[@manavmohata1240]

Also you dont need to make extra vector. Just start from sum/2 towards 0 and first true value will be the required s1

[@praneethkaturi9321]

@@manavmohata1240 yup

[@rakhighoshsarkar9211]

Yes, minimum of range - 2s1 can be written as maximizing s1

[@a.yashwanth]

Taking minimum can be visualised in a number line as the distance between 2 points ie, S1 and S2 should be minimum. Which makes the s1 that is closer to center minimum.

[@SahilSharma-vl9rk]

WOAHHHHHHHHHHH I was able to solve the question just seeing the video till 6:04 Brute Force: Make all subsequence but that will result in time complexity of exponential In brute force, once you have made all the subsequence you just need to accumulate that particular subsequence and take a remainder as the total sum-sum of accumulated subsequence. After that make a variable ans = INT_MAX and put the minimum of total-remaining. Optimized: Try thinking of subset-sum where we take sum as the total sum of all the numbers in the array. Time Complexity = O(n*total) where total = sum of all the elements in the array. C++ Code : int minDifference(int arr[], int n) { int total = accumulate(arr, arr+n, 0LL),ans = INT_MAX, dp[n+1][total+1],remaining; memset(dp,0,sizeof(dp)); for(int i=0;i

[@rakeshkumarsingh4449]

Please take note that this strategy only works for an array of elements that are positive. Great job @Aditya, this playlist is very helpful & easy to understand.

[@priyanshu.tiwari]

after you get the vector, then the maximum of that vector will always be the answer as in (Range - 2*s1), everything is constant except s1, so to minimize it, we need to choose the largest s1 value.

[@shashankgupta29]

@@ansumanmishra1757 Can you Please elaborate?

[@shadowofthecorpse9481]

@@ansumanmishra1757 but we want to return only the minimum difference between subsets, so how does it matter if there are repeated numbers in the array?

[@ansumanmishra1757]

@@shadowofthecorpse9481 yeah , you are right . My bad. I did a pretty similar problem on codechef where we had to print the total number of such minimum difference. So i messed up . Thanks :)

[@Vikas-hk2ll]

Yup, no need to find the minimum, just take the last element of vector with half size, that'll be your S1. BTW, Great stuff Aditya!

[@prakharagarwal4933]

Ya I was also thinking the same..

[@ankoor]

Wow! Great explanation. I am glad that you are explaining how you are developing DP solution rather than filling a table with some formula that most other KZbinrs do when they solve DP problems. After watching those videos I was clueless and frustrated about how the formula shown in those videos was derived. I am glad that I watched your DP Introduction video. After watching 0/1 Knapsack video, I subscribed to your channel because your content is AWESOME! I am pretty sure you will get many subscribers soon. Thank you for taking the time and effort in developing these videos.

[@TheAdityaVerma]

I am really glad you noticed the difference between me and other youtubers who just teach for the sake of making videos. Please share and help this channel grow brother !! BTW one question, how did you land on my DP Intro video?

[@ankoor]

@@TheAdityaVerma For learning DP I watched MIT 6.006 Introduction to Algorithms DP videos (more theoretical but good), Abudul Bari's Algorithm videos (he is pretty good for basics and other algorithms but for DP he also started with filling table) then I tried to solve DP problems on LeetCode and I got stuck so I searched for interview related DP problems and then landed on Tushar Roy DP (garbage explanation), Jenny (table filling only), Back To Back SWE (he explains well but did not link Knapsack variations, not many problems), a few chinese KZbinr videos (difficult to understand as even they were speaking English they were not explaining well) and few other videos and recently 2-3 weeks ago I had seen your channel on KZbin search for DP videos, I clicked on a random DP video in your DP playlist and did not understand what is going on. Then I was reading comments on Tushar Roy's DP video and there someone shared your DP playlist and said start from the beginning and you wont be disappointed, so I watched your DP Introduction video, then 0/1 Knapsack video and then I realized that your DP videos are the BEST on KZbin!

[@yadneshkhode3091]

@@ankoor did you crack any FANG company ?

[@ankoor]

@@yadneshkhode3091 Unfortunately not because of speed. I am able to solve problems but I need to work on speed...

[@yadneshkhode3091]

@@ankoor ohh me too I am also trying ..

[@dmitriegorov9815]

Please take a series on how to approach ad hoc DP problems. Problems that are not standard. This series is really great and helpful. Thanks!

[@TheAdityaVerma]

Thanks, Please share !1

[@saptarshidas2174]

When you realize your teacher is teaching the concepts so good that you come up with the approach in 10 mins without seeing the video . I still don't know how i figured out that let's take the sum of the whole array than divide it by 2, and find out the maximum subset sum in the array which is less than or equal to (total_sum/2) and thn take the absolute of total_sum and max_subsetsum. Thankyou so much @Aditya sir for this greate playlist . You are truely a DP god.

[@atithikumari9411]

Hi Aditya, nice lecture series. Its the first DP series i have started watching and with every upload i m still interested in watching. great work Also quick question, could you mention what would be the changes in case of negative values present in the array for minimum subset sum difference. thx!

[@lakshaydutta2299]

words cant describe how much happy i am that i came across your channel !you are really doing a great job ! your methods of approaching the problem are so good .you are actually teaching how to approach the problem and that is what sets you apart from the rest of the channels on KZbin !thank you so much !saw your profile on linked in and directly sent you a connection request would be really happy if you accept it !!! thank you again !

[@TheAdityaVerma]

Thanks Lakshya, and you meant linkedIN right and not linked list?! 😂 Do subscribe and share the content to help the channel grow !!

[@lakshaydutta2299]

@@TheAdityaVerma 😂😂😂yeah ! Sorry typo*😂😂😂

[@karanbhatia6712]

Another approach that one can observe from this is, to minimize range - 2*S1 we need to maximize S1. Also, S1 is less than range/2 so we can just use the Knapsack directly with weight array as given array and value array also as given array but the capacity of the knapsack as range/2. This finds the maximum subset-sum below range/2. Thus, we can just return range - 2*S1 directly. This reduces the space complexity by half.

[@pratyushnarain5220]

excellent concept bro

[@mayukhchatterjee5998]

@@pratyushnarain5220 the weight array should be the, sums array of range/2 na?

[@bivashyadav7975]

That's how I approach at first too.

[@atishayjain2205]

summing up what we did is the best part of these tutorials which a lot of youtubers and even paid course's teachers miss out on. Seeing 40+ min video tutorials can make anyone forget small details but summing up what we did after each new step is the best thing that you have done.

[@rohittuli8908]

Very nice way of explaining.. thanks a lot for making this series. Its very helpful for people like me who are preparing for intern interviews. Please make a similar series on graphs and heaps also.. And please try to make videos shorter (around 15 mins)

[@TheAdityaVerma]

Heap is already there brother, check out my channel !!

[@AmimulEhsaan]

What an inordinately terrific teacher...Love you man :)

[@raghvendradhakad4718]

Bro only one line can describe you "Everybody is a gangster until a real gangster walks into the room"

[@AdityaKumar-sq6hx]

Best explanation to a DP problem i have seen till now

[@shivangishukla2629]

Please it's a request. make videos on Graph related questions! and cover topics like dfs, bfs

[@ViralAgrawal12321]

yes bhaiya please for(i=0; ;i++) { cout

[@a.yashwanth]

@@ViralAgrawal12321 Time limit exceeded!😂

[@ViralAgrawal12321]

@@a.yashwanth 😂

[@adityaperiwal4819]

You don't know but you may have revolutionized the way computer programming has always been taught. Your youtube channel is a slap on 99.9% computer programming professors in India.

[@manishsinghsaini4399]

Hey Aditya. First of all, great stuff! Intend to watch this entire series. For this particular problem, I have a doubt: why can't we just try to find x, where x is the largest subset sum possible

[@anonymousreviewer3816]

exactly like 0/1 Knapsack.. Yes, we can do that.. It is much much simpler

[@KeshariPiyush24]

Optimized JAVA Solution:) class Solution { public int minDiffernce(int arr[], int N) { int sum = 0; for (int i : arr) sum += i; int columns = (int) Math.ceil(sum / 2.0); boolean[][] dp = new boolean[N + 1][columns + 1]; for (int k = (int) Math.ceil(sum / 2.0); k > 0; k--) { for (int i = 0; i

[@utkarshjaiswal7224]

He also did the same way just in a different way..he iterated a loop to find min of range-2x..you will iterate a loop to find max of x..and then return range-2x

[@navroze92]

Bhai aise insights na hi top coder na geeksforgeeks na baki ke youtube channels dete hai. Very well explained bro keep doing what you are doing!!

[@lifeexplorer2965]

I dont't know how to appreciate you !!!! , Just Awesome

[@TheAdityaVerma]

Thnaks brother !!

[@ichigolameeeee2423]

I started reading the comments before watching this video and it got me intimidated at first but the way you explain is so smooth, that I reach to solution before you show on the lecture. Kudos to the work you have done.

[@vishalsiddha6637]

This might help you guys. CODE:-(NO need to take a vector for all possible sum just take the last value.) vector dp(n + 1 , vector(sum / 2 + 1 , false)); for (int i = 0 ; i < n + 1 ; i++) { dp[i][0] = true; } for (int i = 1 ; i < n + 1 ; i++) { for (int j = 1 ; j < sum / 2 + 1; j++) { if (arr[i - 1]

[@mohdfaisalquraishi8675]

bhai runtime error arha tha mera toh. similar hi kiya tha maine bhi

[@PrabhatKumar-de7eo]

bhai thik hua runtime tera??? @@mohdfaisalquraishi8675

[@swarajshelavale4830]

Good...Nice !!

[@himanshuharsh7839]

@@mohdfaisalquraishi8675 agar range negative hoga to runtime error aayega. Leetcode me arr[i] negative bhi hai.

[@BalakrishnaPerala]

​@@mohdfaisalquraishi8675 for last loop we can reduce time complexity , because we know that its always first element coming from right side(from totalsum/2) which is true, that will be our answer, here is the most optimized code. No need even vector/list , no need to traverse dp from front to tsum/2, we can traverse in reverse direction, get first true element in dp, and get min sum using return (tsum-2*j) public int minDifference(int nums[], int n) { // tsum means = total sum int tsum = 0; for(int i=0;i

[@agrawalhimanshu]

Bhaiya bohot ache see samjh aa gya DP ... Aaj tak aisa ache see kissine nhi samjhaya... thanks a lot for ♥️ please upload regular Bhai..appko bohot support karenge...log paise leke bhi itna acha nahi sikhate thanks again @aditya Bhai 💝

[@ShivamSingh-vh1xz]

Best explaination . Can't compare your teaching with others . Only thank you is very less for your efforts .❤️❤️

[@lakshyamehta7529]

Loved the way he solved all the questions just using a single concept we have to understand the question only, we already knew its answer.

[@nagenderswaroopsrivastava3858]

I Madara Uchiha declare you the best DP teacher.

[@adityag22]

theek

[@adarshverma5048]

This playlist follows DP. Great Work Man. Great Work. Kudos.

[@anmolcoolsinha]

Small doubt, instead of iterating through the vector, can we simply take mn=Range-2*v[v.size()-1] for the minimum value?

[@AnshiPatel_official]

Yes we can do that :) sorry I'm watching after 3years

[@PawanKumar-ou1bw]

sir aapse better dp phadane wala nhi dekha aajtak you are really great, jo pattern badi badi organizations nhi samjhpati aap samjhate ho great sir

[@vandanac3098]

One of the best places to learn DP. Great explanation of the logic behind rather than just writing the code. Thanks for being such a great teacher,

[@vishalchauahan6288]

This playlist is pure gold. much much better than paid courses.

[@gsb22]

At 11:50 I got the solution. Awesome approach. This is how hints work in interview. You gave me first hint and I solved it.

[@subhamsantra9831]

Just fall in love with DP ❤. Thanks a lot sir. Make more tutorials on competitive coding. 🧡🧡

[@shresthh]

Your channel is so underrated. I really appreciate your work. Thanks a lot :D

[@sunilkumawat7959]

Thank you for evolving our brains :)😂

[@TheAdityaVerma]

😂😂😂😂😂😂😂😂 Evolution is natural ✌️

[@sumeetsuman7465]

@@TheAdityaVerma are you on twitter?

[@pradhyumnsharma976]

Thank you Aditya bhai.......I am grateful I found your channel Jo concepts college 4 sal me samjha paya aapne mahine bhar me sikhadi Wish youtube ki bhii koi degree hoti.....Thanks a lot for your efforts

[@lakshshergill9637]

PYTHON CODE :- def subset(n, k, arr): dp = [[False for j in range(k+1)] for i in range(n+1)] for i in range(n+1): dp[i][0] = True for i in range(1,n+1): for j in range(1,k+1): if arr[i-1]

[@abrahamlincoln5724]

A little optimized soln similar to yours -> Instead of creating an array to store the last row of dp matrix, 1. create a variable (p) 2. loop through the last row of dp from sum/2 to 0, i.e for(i = sum/2; i >= 0; i--) 3. check if the elem in the dp is 0 or not. If not, then store 'i' in the variable 'p'. 4. return p.

[@kaushikg1996]

Concept explanation and the way you generalize and basket the problems is amazing. I have watched almost all of your playlists. Absolutely amazing content in each of them 👏.

[@namanagarwal5416]

I approached this problem like a 0-1 knapsack problem, except that value array and weight array both are same and you have to maximize value while keeping the weight below total/2. Made it much easier to understand.

[@balipavankalyan5008]

No words bro To appreciate... Keep going

[@TheAdityaVerma]

Thank you, I will

[@sarveshverma7378]

Nice video Aditya. Very lucid and natural way to solve the problems. We can optimize the search for for max S1 that minimizes Range - 2*S1. Simply start the loop from half the vector size and iterate towards left. When we get first true, we get the required candidate and we an simply return from the loop. It won't need maintaining a min value variable too.

[@kirtikhohal3313]

Jist of the logic used in the solution (in the end this is quite different from Aditya’s solution, and also more easy to understand):- 1. We need to partition the array into two subsets such that the difference of their sum is minimum. For that, what we have done is first we don’t know what the sum of these two partitions will be, we don’t have any idea about the candidate sums of the subsets of the array. So, first we need to find all the candidate sums. 2. To find all the candidate sums, we know that the minimum sum possible is 0, and the maximum sum possible is the sum of the whole array (which he’s calling as range), all the candidate sums will lie into this range (0-sum). So, after finding the total sum (range), pass this into subset sum function, which will give you a 2D matrix. 3. In this 2D matrix, the last row signifies which number is possible as sum out of all the numbers in the range (0-range), so we’ll only work with the last row of the matrix, true value means this number is making a sum, and a false value means this number is not making a sum. 4. Also notice that in the last row, through the first half of the row, we can retrieve the other half, like range-s1 will give me the value in the other half, and range -2*s1 will give the difference between these two values. Also you can notice that the possibility of minimum difference is more likely in the middle of this last row, because two middle elements are more likely to be close to each other than two elements which are lying at the ends of the row. The difference between these two middle elements is more likely to be less than the difference obtained by a pair which are far from each other. So, what we can do is we can run a loop starting from the middle of the last row to the 0th index of the last row. And then checking if its making a sum (or if it is having a true value), then doing sum-2*s1, which will give me the desired minimum difference. The moment I’ll get this difference I’ll come out of this loop, because if I’ll keep on traversing the backward side, the difference will only increase, because, as I’ll move towards 0th index, I’m encountering a pair which are far from each other, and thus they’ll give me a big difference as compare to a pair which is closer or equal to the middle number. Below is my gfg code:- int minDifference(int arr[], int n) { int sum=0, diff=INT_MAX; for(int i=0;i

[@uttam5518]

very well explained

[@because2022]

Great teaching. You are very good in interconnecting things and making things very easy to understand.

[@RahulKumar-uc1lj]

This code is not dealing negative numbers!!! Would u please help?

[@sanchitxs]

Amazing explanation!! I addition in the final step to check for value of S1 we can directly do from t[n+1][sum/2] to t[n+1][0] and if we encounter a true we can break out and that is out S1. we can thus return sum - 2s1

[@ajitshiva3282]

Please try to make videos shorter(around 15mins). Btw you're a great teacher.

[@PeaceLoveAman]

yeah! No need to repeat the explanation, Because it is a video one can go back and watch again if he/she is getting it.

[@harshkant8217]

nice explanation!! hats off!! but we can find answer without even using a vector, just iterate backwards from range/2 unless you find a true cell int s1=range/2; while(dp[n][s1]==false) s1- -; return range-(2*s1); hope it will help.

[@vivekpurushothaman8]

Really appreciate your detailed work and effort put behind each video. One question. You loop through the vector from 0 to sum and then find the minimum right. Instead if we reverse the loop to start from mid to zero, the first occurrence of it is the candidate for minimum sum. Am I missing something?

[@vidyabhushan7655]

No, this approach is also fine.

[@AnandVerma]

I solved this problem by target sum approach. I just watched your Knapsack video and solved all its variants on my own without watching the rest of your videos! You are great!!

[@ishan7824]

My approach was slightly different (The concept remains the same) First of all we will find sum of all the elements in the array and divide it by 2. Now, we just have to find a subset whose elements sum upto some value which is closest to the above value we got (sum/2). This is basically a raw 0-1 Knapsack problem now where the value (sum/2) is the maximum capacity of our bag and weights are given in the form of array elements. After we get the maximum closest value from the above algorithm, we can just find our answer by ((sum of all elements) - 2 * maxClosest)

[@ammarranapur5917]

yeah i also solved it in this way, instinctively this is the first solution that comes to mind , i dont know why he didnt adopt this straightforward method.

[@kola9834]

@@ammarranapur5917 can you please provide the code that you solved for this problem!!

[@advaitbajaj4241]

If y'all have solved this way could you please provide the code

[@shubhamkeshri8430]

Sir ji Tussi great ho 😎😉😘. Simplest explanation . If someone is not getting this then he has to forget about programming.

[@sonams4923]

Really amazing. Never thought like this :) Would be great if you can explain time complexity at the end. P.S. Looking forward for many more videos!

[@tinukumar41]

your explanation and way of teaching is great and the most important thing i like is that on one topic you making a series of video which clear all concept it is just awesome

[@dakshdolka800]

Why we have to run that last loop when you get highest value of s1? We can simply put that formula(min difference= range -2*s1)

[@adityahridyam7698]

yes same qs?

[@venkatkrishna3774]

The given initial array may have negative integers so the for loop is needed to find maximum s1 in the vector array.

[@akashgkrishnan9596]

One of my friends told me about this channel and he was sure i will learn dp from these videos and boy he was right. i have started forming intuition cause of you. thanks mahn

[@ajitdhayal1612]

Ye dislike vhi kerte hai jo pichle videos dekhe bina direct ish video per aate hai!!!

[@p.adityakumar1762]

Honestly speaking, you're videos on dp are the best on youtube. I actually didn't need any help in all of the knapsack variation problems to solve them, because of the way you explained the very first knapsack(basic one) video and the video in which you explained how to recognize and solve a knapsack variation. I wanted to say that it would help a lot if you would write down the constraints as well according to you, so that we could think about the problem accordingly.

[@meghnavarma6597]

Great explanation, Sir... I had just one doubt though... Is there a need to form a vector array ? Can we not use a variable, say v, to store the maximum subset-sum that can exist in the first half of the range and then return (range - 2 * v) ?

[@saarthakkhandelwal4256]

Yeah ofcourse you can do this. Aditya just did it for the students to make it more understandable .

[@himanshukhairajani]

I used to be afraid of DP and once i saw your videos...my fear turned into interest ...such a crisp-and-clear explanation made me realize that-> fundamentals concepts in mind makes things work so smoothly instead of just mugging up the code

[@masters_akt]

Great work!! I figured out that we can optimize the last step by just considering the last true box from n/2 moving backward. int x = sum/2; while(!t[n][x]) x--; return sum-2*x; This code can be replaced by the last for loop. Although it won't affect the asymptotic time complexity but will definitely contribute to the actual running time of the algo. Ques: What can be done to this code for negative numbers?

[@rohannyati8144]

Ya somene plz tell what should be done in case of negative numbers in array....leetcode ques no. 2035

[@janvisingla3746]

This is the first time i am commenting on any video, just cant stop myself .Your way of teaching is unique from all the KZbinrs and i must say its "BEST". Thank you so much sir :)

[@mradultiwari5820]

Is this pseudocode correct for this problem? arr=[given array of items] arr.sort() //increasing order n=length(arr) a=0 b=0 for i in range(n-1,-1,-1){ // i will reduce by 1 from n-1 to 0 in //each iteration. if (a

[@shadowofthecorpse9481]

nope, this method will fail in some cases of repeated inputs. For eg: if arr = [3,3,3,4,5], we will end up with a = 10, b = 8. So effectively a = 4+3+3=10, and b = 5+3=8. This method will return difference as 2. However, a better split of a = 3+3+3=9 and b=5+4=9 exists, which will return difference as 0.

[@mradultiwari5820]

@@shadowofthecorpse9481 hmmm😐 It's not working in repeated cases... Anyways, Thanks for correction 🙂

[@tanisha3613]

Aise to ni, bt i guess, after sorting subtract highest no, see diff, repeat till res is -ve, in case of -ve, break the loop and return the res Arr(3 3 3 4 5) Res=18-5 , s2=5, min =res-s2=8 Res=13-4, s2=s2+4, min=res-s2=0 Res=9-3,. s2=s2+3, min=res-s2=-6 Brk the loop, if se phle +ve -ve chk krna h I hope this is correct

[@adarshsasidharan254]

Great video Just two things: 1. Instead calculating subset sum for the sum of all values, we can calculate subset sum for sum/2. 2. Instead of creating a vector and iterate through all of its elements, just iterate from last value(sum/2) and if True break because that would be the min diff

[@rishabsaini8347]

I had the same intuition about the problem. 😄

[@PrashantKumar-gg5qd]

thank u for so much effort

[@TheAdityaVerma]

Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️

[@vrajsoni7610]

A small doubt : The minimum ans would always be Range - 2x where x is the largest possible value in the vector that you formed with the last row of dp array having True values? Appreciate your efforts. Thanks for helping lots of people out.

[@hacksight3567]

subsetsum() can be passed with range/2 Part after subsetsum() can be more optimized: for(j=range/2;j>=0;j--) { if(dp[p][j]==true) { break; } } int answer=range-(2*j); return answer; No need to store in any vector and then find minimum....

[@adityan5302]

Good job

[@DeepanshChawla_]

Bro you are pro....even i was thinking the same😅

[@Arjun69]

Brilliant. If u didn't understand in the starting wait till the end of the video , u will get it.

[@lifecodesher5818]

having pain in my head.oh wait my brain is evolving

[@TheAdityaVerma]

lmaaoo

[@anishaggarwal7478]

sir we can also start a loop from range/2 to 0 and check whichsoever i fulfils the subsetsum function for the given arr we print (range -2*i) that will be our answer. That way it is just a extension of subset sum;

[@tusharkumar6566]

Cracked version download kar le bhai watermark nahi aaega , or is comment mai ID meri hai words mere friend ke hai.

[@ishitamishra6279]

THANK U BRO!

[@adityakhare9577]

bhai crack version link ????

[@ishitamishra6279]

@@adityakhare9577 bhai isne link upload off kr rkha hai, kya kren aap btao?

[@adityagarg1662]

@@ishitamishra6279 all copyrights reserved by abdul pandat.

[@adityakhare9577]

@@ishitamishra6279 sed lyfe😑

[@pradeepmondal4943]

Bhai aap kya padate ho 😘😘 ekdam jakkas ...😘😘😘😘😘😘 .. love u brother from Banglore ..

[@sutanubhattacharya6307]

I have been watching your videos since a couple of days. Your style of teaching is fantastic. I am really enjoying DP. Will be waiting for more videos!!

[@rambaldotra2221]

Probably nobody other than you can explain so smoothly such an important concept..Thanks For Sharing your wonderful knowledge ✨

[@tushartiwary2348]

Chacha pranam Bahut aacha padhate hai aap Sawal dekh k dar gye the hm, par video dekh k aacha lga Subscribe kar diye h aapko🙏

[@phanichowdary7928]

Bro - i really appreciate the way you presenting the concept....this is really helping to understand concept..Thanks a lot for making these videos and hope expecting more videos like this

[@aryangupta867]

I just think this problem is the exact Knapsack problem 0/1 as here the value array is the weight array itself which means it is the given array of numbers. So, if we just find the (max profit in case of Knapsack) and fill the dp array. Then if we return dp[n][sum/2]. It will give maximum profit which is max possible sum(if we consider value array as a given array of numbers itself) till sum is sum/2. So, just solve it by using Range-2(max sum returned from previous function) just to avoid overhead of storing the last row again to a vector. So, an optimization in terms of space complexity happens here. Anywayss the way you connected the topic is simply amazing!!!

[@palashdeepsingh2559]

Looking for this comment for so long lol. Thought about this approach only

[@satishkr7678]

Kudos to you. Explained the complex topic so easily.

[@akashkumarsingh5355]

i bought a course to learn dp and whenever i didnt understand anything i used to come on youtube understand it and then back to the course videos...i dont remember how i landed on ur videos...but after watching ur videos i have not watched any of my course videos...

[@shreenavkhandelwal4168]

Thanks bhaiya, it's the first time I coded any hard problem on gfg by myself completely and got it correct. Only because of you.

[@rohitsingh-yq3sk]

just stumbled on this playlist, now I'm going to watch it complete. Awesome way of teaching. Stay motivated and keep making such videos.

[@sagargoyal6993]

Your DP playlist is itself a DP

[@himanshushekhardas1730]

your explanation is too awesome, can't ask for more, A BIG THANKS FOR YOUR VIDEOS !!!!

[@ritikkumarjain2094]

Hats off!!!!!!! No words to say. No man can give such a great content even after taking money!

[@akhiljain1695]

Hats off to the way you build the intuition and relate the problem to another already known problem.....Amazing explanation bro. Thanks a lot.

[@rahulajmeria6906]

30:30, "subset sum yaad hai kese krte hai? me ni kaar ra, actually me mai ni kr ra" 30:49, "ab me bata ra hu ki subset sum kese krte hai" best teacher ever yaar sab revise bhi kara dete hai!!

[@varungoel3633]

mein nahi gin raha matrix ke blocks bol raha tha 😂