در وسط ملاقات کنید

Meet-in-the-Middle

بر این اساس، استفاده از meet-in-the-middle منطقی است اگر دو شرط وجود داشته باشد.
1) زمان لازم برای حل نیمی از مسئله به طور مجانبی کمتر از زمان حل کل مسئله است.
2) با حل نیمی از مسائل، می توان راه حل هایی را برای کل مسئله اصلی و در عین حال به طور مجانبی سریعتر از حل کل مسئله به دست آورد.
 

مثال

بگذارید چهار آرایه از اعداد صحیح A، B، C و D وجود داشته باشد. باید دقیقاً یک عدد از هر آرایه انتخاب کرد تا مجموع این اعداد برابر با صفر باشد. این برای O(n4) کار می کند.

با این حال، می‌توانیم از meet-in-the-middle استفاده کنیم.
توجه داشته باشید که a + b + c + d = 0 معادل (a + b) = -(c + d) است.
بیایید کار را به دو نیمه تقسیم کنیم، یعنی در نیمه اول فقط از آرایه های A و B و در نیمه دوم فقط از C و D.
بیایید روی تمام گزینه های ممکن (a + b) در نیمه اول تکرار کنیم و همه مقادیر را در یک جدول هش ذخیره کنیم (unordered_map, HashMap یا مانند آن.). این در O(n2) کار می کند.
اکنون ما روی تمام گزینه های ممکن (c + d) در نیمه دوم تکرار می کنیم. وقتی گزینه خاصی را در نظر می گیریم، بررسی می کنیم که آیا مقداری در جدول هش مرتبط با مجموع فعلی علامت مخالف وجود دارد یا خیر (سپس دو عدد متقابل پیدا کردیم که مجموع آنها صفر می شود). این بخش در O(n2) نیز کار می‌کند.
ما در اینجا یک مرحله جداگانه "ادغام پاسخ" نداریم. در یکی، ما این کار را در دوره حل برای هر یک از نیمه ها انجام دادیم. اکثر وظایف وضعیت مشابهی خواهند داشت.
ما به یک راه حل در O(n2) با استفاده از meet-in-the-middle رسیدیم.

شایان ذکر است که meet-in-the-middle اغلب برای بهینه سازی راه حل های نمایی استفاده می شود که به طور قابل توجهی بر زمان اجرا تأثیر می گذارد.