Meet in the middle algorithm

This video explains the meet in the middle algorithm which is a very unique algorithm used to find the closest subsequence sum. It requires you to know finding all possible subset sums and use of binary search lowerbound. A practice problem for this algo is leetcode 1755.
CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
======================================PLEASE DONATE=============================
🧡 SUPPORT OUR WORK: / techdose
💚 UPI-ID: surya.kahar@ybl
💞JOIN Membership: / @techdose4u
==============================================================================
INSTAGRAM : / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
USEFUL LINKS:
🟠Must do TIPS to ACE Virtual Interview: • 🔴Must do Tips to ACE y...
🟢Best strategy to excel your coding interview: • 🔴Best strategy to exce...
🟡Get your dream job in 1 month: • 🔴Get your dream job in...
🔵How to crack dream job in just 2 months: • How to crack dream job...
🟣7 Days DSA plan: techdose.co.in...
RELATED LINKS:
CODE LINK: gist.github.co...

[@sumitkumarmahto5081]

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 ?

[@saumyaranjan9256]

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!

[@surendharv795]

4:04 Sir, One Small correction in the video.
The closeset sum can be great than the goal , but should be closest.

[@casinarro]

really neat and systematic explanation. This channel is a gem!! Thanks a lot, will continue watching and refer the channel to my friends.

[@techdose4u]

Welcome :)

[@hijibiji9471]

lower_bound definition is different if compared with lower_bound stl of cpp

[@HimanshuSingh-rm5sd]

yes it gives arr[i] > = target with smallest i value

[@jui20oct]

Very clear explanation! Thank you!

[@shivanggautam541]

very understandable and amazing explanation. thank you very much for the video

[@HimanshuSingh-rm5sd]

@techdose sir lower_bound definition is different in this case for 13 it wil return n size of array

[@yogeeshrsyogeeshrs4204]

Yes I am also requesting you to make videos on greedy technique it will be beneficial in the interview please

[@techdose4u]

Sure

[@sonumondal9376]

One request sir your videos are really beneficial but can you make more videos for greedy playlist plzzz plzz

[@techdose4u]

noted

[@sdmfslkdm]

how does deviding the arrray into two parts explore all subset sums ?
for eg -> 3 + (-2) = 1 is missing !

[@techdose4u]

What’s your example?
Please elaborate

[@harisai3580]

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

[@techdose4u]

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!

[@vivekpatwal4655]

beautiful sirrr

[@bharat_india12]

Good explanation

[@amboojmittal2993]

We have considered time complexcity of sorting the right half

[@techdose4u]

Yes

[@Lucifer-xt7un]

Sir please please upload a sheet for complete beginners which support to join your course

[@ayushsaxena5505]

In the code why have you also used the previous element of the lower bound

[@jatinarora2991]

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 ?

[@techdose4u]

Space complexity ?

[@kushalkushal8458]

Thanks a lot

[@siddharth892]

Why would the dp not work though?

[@AnujGupta-xi5ep]

For negative elements in the array, dp matrix can't store negative index, hence it won't work.

[@deepesh16b]

YOU SAID WRONG DEFINITION OF LOWER BOUND. IT RETURNS EQUAL OR JUST GREATER VALUE

[@techdose4u]

yes correct :)

[@pratyushbhatt1712]

Your lower bound terminology is wrong. You are mixing Floor of an array with lowerBound.