The video's Heading is Meet in the middle algorithm, but you never really explained why this is called meet in the middle algorithm ? what is the intuition behind it ? how can this idea be generalized to other such problems ?
Really clear and concise on the explanation part. The thing which helped most was the way in which you had prepared the notes beforehand and they really addressed every part of the problem and the algorithm as to why is it beneficial to use this in this particular case. Thank You!
Anybody seeing my comment pls answer my doubt that is subset sum problem works only for positive numbers right or it works for any integers ? pls........
It can be made to work but the complexity will be much more. Ex. (-2,-4,2,3) Sum range will be -6 to 5 (taking extreme subset sum scenarios). Now, cols must denote sum. So, No of cols = mod(6)+mod(5)+1(for 0) = 12 cols -6 will be made to map to 0. You can note that space complexity is large. If a sum goes beyond target sum still it can come back due to negative numbers ahead. Therefore, if you give enough space then YES you can solve it :) Peace!
why subset sum is not a feasible soln can you explain. If we use binary seach with subset sum(using dp) then it can be solved in log(sum)*sum*N right ?
The video's Heading is Meet in the middle algorithm, but you never really explained why this is called meet in the middle algorithm ? what is the intuition behind it ? how can this idea be generalized to other such problems ?
Really clear and concise on the explanation part. The thing which helped most was the way in which you had prepared the notes beforehand and they really addressed every part of the problem and the algorithm as to why is it beneficial to use this in this particular case.
Thank You!
Very clear explanation! Thank you!
lower_bound definition is different if compared with lower_bound stl of cpp
yes it gives arr[i] > = target with smallest i value
really neat and systematic explanation. This channel is a gem!! Thanks a lot, will continue watching and refer the channel to my friends.
Welcome :)
4:04 Sir, One Small correction in the video.
The closeset sum can be great than the goal , but should be closest.
very understandable and amazing explanation. thank you very much for the video
Yes I am also requesting you to make videos on greedy technique it will be beneficial in the interview please
Sure
@techdose sir lower_bound definition is different in this case for 13 it wil return n size of array
beautiful sirrr
Good explanation
One request sir your videos are really beneficial but can you make more videos for greedy playlist plzzz plzz
noted
We have considered time complexcity of sorting the right half
Yes
how does deviding the arrray into two parts explore all subset sums ?
for eg -> 3 + (-2) = 1 is missing !
What’s your example?
Please elaborate
Anybody seeing my comment pls answer my doubt that is subset sum problem works only for positive numbers right or it works for any integers ? pls........
It can be made to work but the complexity will be much more.
Ex. (-2,-4,2,3)
Sum range will be -6 to 5 (taking extreme subset sum scenarios).
Now, cols must denote sum.
So, No of cols = mod(6)+mod(5)+1(for 0) = 12 cols
-6 will be made to map to 0.
You can note that space complexity is large.
If a sum goes beyond target sum still it can come back due to negative numbers ahead.
Therefore, if you give enough space then YES you can solve it :)
Peace!
Sir please please upload a sheet for complete beginners which support to join your course
In the code why have you also used the previous element of the lower bound
why subset sum is not a feasible soln can you explain. If we use binary seach with subset sum(using dp) then it can be solved in log(sum)*sum*N right ?
Space complexity ?
Why would the dp not work though?
For negative elements in the array, dp matrix can't store negative index, hence it won't work.
YOU SAID WRONG DEFINITION OF LOWER BOUND. IT RETURNS EQUAL OR JUST GREATER VALUE
yes correct :)
Your lower bound terminology is wrong. You are mixing Floor of an array with lowerBound.