10 Minimum Subset Sum Difference
ฝัง
- เผยแพร่เมื่อ 4 ก.พ. 2020
- Sum of subset differences
Given a set of integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.
If there is a set S with n elements, then if we assume Subset1 has m elements, Subset2 must have n-m elements and the value of abs(sum(Subset1) - sum(Subset2)) should be minimum.
Example:
Input: arr[] = {1, 6, 11, 5}
Output: 1
Explanation:
Subset1 = {1, 5, 6}, sum of Subset1 = 12
Subset2 = {11}, sum of Subset2 = 11
PROBLEM STATEMENT LINK:www.geeksforgeeks.org/partiti...
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
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.
![ไหล่อ่อน (Soft Shoulder) - Atom ชนกันต์ [OFFICIAL MV]](http://i.ytimg.com/vi/HUWl53msBQY/mqdefault.jpg)
![[SUB] 베몬이 교관님 멘탈을 탕탕 후루후루~٩(๑❛ᴗ❛๑)۶ FOREVER 웃게 되는 갓기들의 수련회 | 돌들의침묵 | BABYMONSTER(베이비몬스터) 'FOREVER'](http://i.ytimg.com/vi/FISAO7BwIxE/mqdefault.jpg)
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
yeah man found that after an hour of debugging :(
This comment should have more likes
you mean should we use the iterative approach and not the recursive approach?
i done this problem by memoization
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
Today , i realized views can't decide the level of the videos...
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 !! ✌️❤️
@@TheAdityaVerma please do it asap please
@@TheAdityaVerma Can you please include the explanation of Tree and Graph related concepts too when you get time in the month of May? :)
yes we want videos on graph
@@TheAdityaVerma bhai may aa gaya, graph aur tree ke videos kab aayenge bhai??
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.
really?
awesome man
If we can think this, means the trainer is excellent.
hi
😯WOW
referral dede bro
Interconnection between the questions is the best part in these tutorials... 😊
I can say without a doubt that "Aditya Verma is god of DP" 😜. Great Work man!
Yes he is
At least make the 'g' capital! :-)
@@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! :-)
You probably don't know about red coders then
@@zarc5744 it's about the communication.
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 :)
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
@@yogesh970 obviously
i am thinking the same.. thanks for the confirmation
@@yogesh970 can you please explain why time complexity will not decrease
@@amansinghgautam9578 because constant multiples don't effect the time complexity on a very big scale
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.
clever approach bro
even i thought the exact same thing !
@@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
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
TRY this Leetcode - 2035 (Hard) Acceptance Rate - 19.9%
Seriously I have seen lot of other programming channels on TH-cam.. 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.
Last part could be solved efficiently: -
int size=v.size(); // v is the vector as mentioned in video
cout
How would you store the last row from table to a vector .....
@@AmandeepSingh-ot6st as mentioned in video
I thought same bro 🙄
Yeah you're right return range - 2*vector[vector.size()-1];
Won't make a difference on the overall complexity so its fine man. This way it is easier to understand for all.
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
Arigato !
thankyou so much buddy for sharing the code , i was getting some errors.
thanks buddy :)
arigato
its not working on leetcode
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 !!
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.
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.
excellent concept bro
@@pratyushnarain5220 the weight array should be the, sums array of range/2 na?
That's how I approach at first too.
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.
@@ansumanmishra1757 Can you Please elaborate?
@@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?
@@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 :)
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!
Ya I was also thinking the same..
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.
just stumbled on this playlist, now I'm going to watch it complete. Awesome way of teaching. Stay motivated and keep making such videos.
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?
You're right
Also you dont need to make extra vector. Just start from sum/2 towards 0 and first true value will be the required s1
@@manavmohata1240 yup
Yes, minimum of range - 2s1 can be written as maximizing s1
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.
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]
bhai runtime error arha tha mera toh. similar hi kiya tha maine bhi
bhai thik hua runtime tera??? @@mohdfaisalquraishi8675
Good...Nice !!
@@mohdfaisalquraishi8675 agar range negative hoga to runtime error aayega. Leetcode me arr[i] negative bhi hai.
@@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
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.
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
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!
Thanks, Please share !1
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.
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!!
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.
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 TH-camrs 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.
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?
@@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 TH-camr 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 TH-cam 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 TH-cam!
@@ankoor did you crack any FANG company ?
@@yadneshkhode3091 Unfortunately not because of speed. I am able to solve problems but I need to work on speed...
@@ankoor ohh me too I am also trying ..
Just fall in love with DP ❤. Thanks a lot sir. Make more tutorials on competitive coding. 🧡🧡
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
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 TH-cam !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 !
Thanks Lakshya, and you meant linkedIN right and not linked list?! 😂
Do subscribe and share the content to help the channel grow !!
@@TheAdityaVerma 😂😂😂yeah ! Sorry typo*😂😂😂
Please it's a request. make videos on Graph related questions! and cover topics like dfs, bfs
yes bhaiya please
for(i=0; ;i++)
{
cout
@@ViralAgrawal12321 Time limit exceeded!😂
@@a.yashwanth 😂
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!
I have not seen any one explaining any concepts so well. Content is really organized well. Loved the way you are correlating problems 🙏🙏🙏. Thanks a lot
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!!
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,
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
Yeah you're right
I came to comment the same dude 😂😂😂 @Aditya Verma should pin this.
Your channel is so underrated. I really appreciate your work. Thanks a lot :D
This is the first time i am commenting on any video, just cant stop myself .Your way of teaching is unique from all the TH-camrs and i must say its "BEST". Thank you so much sir :)
Best explaination . Can't compare your teaching with others .
Only thank you is very less for your efforts .❤️❤️
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)
Heap is already there brother, check out my channel !!
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 (
The way you approach the problem is to be appreciated. And You make me understand better than any one else. Thank you bro !!
Bro only one line can describe you "Everybody is a gangster until a real gangster walks into the room"
I dont't know how to appreciate you !!!! , Just Awesome
Thnaks brother !!
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.
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.
I Madara Uchiha declare you the best DP teacher.
theek
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 👏.
Probably nobody other than you can explain so smoothly such an important concept..Thanks For Sharing your wonderful knowledge ✨
Hats off to the way you build the intuition and relate the problem to another already known problem.....Amazing explanation bro. Thanks a lot.
Small doubt, instead of iterating through the vector, can we simply take mn=Range-2*v[v.size()-1] for the minimum value?
Yes we can do that :) sorry I'm watching after 3years
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
exactly like 0/1 Knapsack..
Yes, we can do that.. It is much much simpler
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
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
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
Your DP playlist is itself a DP
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!
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]
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!!
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
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) ?
Yeah ofcourse you can do this. Aditya just did it for the students to make it more understandable .
This code is not dealing negative numbers!!! Would u please help?
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.
This playlist follows DP. Great Work Man. Great Work. Kudos.
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?
Ya somene plz tell what should be done in case of negative numbers in array....leetcode ques no. 2035
Thank you for evolving our brains :)😂
😂😂😂😂😂😂😂😂 Evolution is natural ✌️
@@TheAdityaVerma are you on twitter?
@Aditya Verma ,as S1 have always to be less than range/2 so ultimately min(range-2*s1) means finding max value from the vector(0,range/2)
you could also make table upto sum/2 as dp[n+1][(sum/2)+1] and we also dont need vector as we could traverse the last row from j = sum/2 till j = 0 and the moment we get true, we return (range-2*j).
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)
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.
@@ammarranapur5917 can you please provide the code that you solved for this problem!!
If y'all have solved this way could you please provide the code
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
very well explained
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;
I was able to solve a codchef contest ques using this video even though I have been learning DP for just two days. Thank you bhaiya for such great content. I really like the part where you teach us how to think rather than mugging up the solution. 🔥
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)
yes same qs?
The given initial array may have negative integers so the for loop is needed to find maximum s1 in the vector array.
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?
No, this approach is also fine.
One thing, i was thinking that,
Can we do this without DP, and in a better way?
Like, lets sort the array ascending order.
Then check the difference(minimum) of largest one, and the rest all, then include the largest and smallest, and rest all check difference then include largest smallest, 2nd smallest and rest all..and so on (obviously we will be taking help of prev sums to find subsequent sums)..., since by logic we can prove that the optimal soln will be some combination of (largest and smallest and smallest's consecutives) and the rest ones. In this way we have to check only n or less, numbers with TC O(x
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.
No words bro
To appreciate...
Keep going
Thank you, I will
Please try to make videos shorter(around 15mins).
Btw you're a great teacher.
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.
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.
At 44:20 , instead of passing the entire range as the parameter to subsetsum(arr, range) we can pass range/2 as the parameter as s1 can have max value till range/2.
Ye dislike vhi kerte hai jo pichle videos dekhe bina direct ish video per aate hai!!!
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
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.
@@shadowofthecorpse9481 hmmm😐 It's not working in repeated cases... Anyways, Thanks for correction 🙂
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
your explanation is too awesome, can't ask for more, A BIG THANKS FOR YOUR VIDEOS !!!!
@Aditya Verma great job man! Best explanation ever! Can you please upload all the videos. I am preparing for my upcoming interviews. This is the best tutorial channel I have come across.
having pain in my head.oh wait my brain is evolving
lmaaoo
thank u for so much effort
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 !! ✌️❤️
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.
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 💝
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....
Good job
Bro you are pro....even i was thinking the same😅
Cracked version download kar le bhai watermark nahi aaega ,
or is comment mai ID meri hai words mere friend ke hai.
THANK U BRO!
bhai crack version link ????
@@adityakhare9577 bhai isne link upload off kr rkha hai, kya kren aap btao?
@@ishitamishra6279 all copyrights reserved by abdul pandat.
@@ishitamishra6279 sed lyfe😑
What a beautiful explanation man. Really hats off.
Thanks for all your efforts towards the community.
Ek number.
Finally i was able to solve this on my own, just used the concept of adding the last row in vector, Thanks @Aditya Verma sir you teach so good.
Each videos are solid gold man. I don't have words to describe
I am seeing your playlist even after solving because I want to rewrite my concept In the way you teach
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
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
We can actually skip the last step(storing values of last column in array and computing minimum). For (Range - 2*S1) to be minimum the S1 value should be largest so we can iterate over the last row of dp and get the last possible index < range/2. Then we can just return ans as (Sum - 2*ind).
In Code this should translate to this.
class Solution{
public:
int minDifference(int arr[], int n) {
int sum = 0;
sum = accumulate(arr, arr+n, sum);
bool dp[n+1][sum+1];
for(int i=0;i
What an inordinately terrific teacher...Love you man :)
Great video!! In last part instead of calculating min among all Range - 2*sum , we can traverse reverse from middle and return Range - 2*sum when we got our first True, as Range - 2*sum will be minimum when sum is maximum.
I didn't know DP or any question can be explained so easily. Keep up the good work brother :) .
Very similar to the knapsack problem, We have to choose a subset out of all possible subsets, such that a given condition is satisfied.
A very easy Recursion + Memoization solution is possible :
/*
sum: sum of the complete array
sum_aside : sum of the elements in my knapsack
initialize all cells of dp vector with -1 before passing it to the function.
*/
int solve(int arr[], int size, int sum, vector& dp, int sum_aside = 0) {
if(size == 0) {
return abs(sum-2*sum_aside); //if size == 0, We have a candidate subset in our knapsack .. just return the difference.
}
if(dp[sum_aside][size] != -1) {
return dp[sum_aside][size];
}
dp[sum_aside][size] = min(
solve(arr, size-1, sum, dp, sum_aside), //not putting the current element into knapsack
solve(arr, size-1, sum, dp, sum_aside+arr[size-1]) //putting the current element into knapsack
);
return dp[sum_aside][size];
}
Please can you send the full code of the memoize version...
Best explanation to a DP problem i have seen till now
Really well taught :) Please upload other dp videos (Dp on GRID, variations of Kadane and others mentioned in 1st video of Playlist.)
Hats off!!!!!!! No words to say. No man can give such a great content even after taking money!