Skip to content

139 — Meet in the Middle

এই level-এর প্রথম problem — অভিনন্দন, boss level-এ পা রাখলে! আগেই বলে রাখি: এই level competitive programming-এর দিকে ঝোঁকা, interview-এর জন্য optional (repo-র plan অনুযায়ী)। তাই চাপ নিও না — মজা করে ভাঙো-আর-মেলাও খেলা শেখো। Meet in the middle হলো সেই কৌশল যেখানে আমরা একটা অসম্ভব-বড় brute force-কে ঠিক মাঝখানে কেটে দুই দিক থেকে এসে মিলিয়ে দিই।

Source

  • Original source: CSES Problem Set — Meet in the Middle (classic subset-sum split technique)
  • Platform: CSES — https://cses.fi/problemset/task/1628
  • Topic: Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
  • Difficulty: Hard
  • Pattern: split + merge (subset enumeration in two halves)
  • Basic idea inherited from: 047, 062 (subset / bitmask enumeration — ../04-bit-manipulation/)

1. Problem in simple words

তোমাকে nটা সংখ্যার একটা array আর একটা target T দেওয়া আছে। জিজ্ঞেস: array-এর কয়টা subset আছে যাদের যোগফল ঠিক T?

ধরো array = [1, 2, 3, 4], T = 5। উত্তর 2 — কারণ {1, 4} আর {2, 3} দুটোরই যোগফল 5।

ছোট n-এ (ধরো 20) সব subset (2²⁰ ≈ 10 লাখ) ঘুরে দেখা যায়। কিন্তু n = 40 হলে 2⁴⁰ ≈ 10¹² subset — এক জীবনে শেষ হবে না। এই problem-টা তাই শুধু উত্তর নয়, একটা চিন্তার ছাঁচ শেখায়: যখন brute force সামান্য বড়, তখন তাকে দুই ভাগে ভেঙে দ্রুত করা যায় কি না।

মনে রাখো — এটা CP-leaning level। Interview-পথে থাকলে নির্দ্বিধায় এড়িয়ে মূল DS topic-এ যেতে পারো; পরে ফিরে এলে বেশি মজা পাবে।

2. What is the math idea?

মূল গণিত হলো exponent ভাগ করা: 2ⁿ = 2^(n/2) · 2^(n/2)। মানে পুরো subset-আকাশ একটা গুণফল — দুটো অর্ধেক-আকাশের গুণফল। আমরা সেই গুণটাকে যোগে বদলে দিই: দুই অর্ধেকের subset আলাদা আলাদা বানাই (যোগফল 2 · 2^(n/2)), তারপর match করি।

আর match-এর কৌশলটা একটা সহজ বীজগণিত: একটা subset-এর যোগফল যদি বাঁ অর্ধেকে s আর ডান অর্ধেকে t হয়, তবে মোট যোগফল s + t। আমরা চাই s + t = T, মানে t = T − s। তাই বাঁ-এর প্রতিটা s-এর জন্য ডানে শুধু T − s খুঁজলেই হলো।

3. Which basic idea does this inherit from?

এটা সরাসরি দাঁড়িয়ে আছে subset / bitmask enumeration (problem 047, 062)-এর উপর। সেখানে শিখেছিলে for mask in range(1 << n) দিয়ে সব subset ঘোরানো — এখানে সেই একই চাকা, কিন্তু পুরো array-তে না চালিয়ে আমরা অর্ধেক array-তে চালাই (1 << (n//2))।

নতুন যেটা যোগ হলো: দুই অর্ধেকের ফলাফল merge করা। আর সেই merge দ্রুত করতে লাগে sorted list-এ binary search (bisect) বা two-pointer — যা আসলে level 7-এর binary search-এরই প্রয়োগ। তাই এই problem দুটো পুরনো অস্ত্রের জোড়: subset enumeration + binary search।

4. Real-life analogy

ভাবো দুই বন্ধু একটা বড় ধাঁধার বই অর্ধেক-অর্ধেক ভাগ করে নিলে। একজন প্রথম 20 পৃষ্ঠার সব সম্ভাব্য উত্তর-নম্বর একটা খাতায় লিখে গুছিয়ে রাখল; আরেকজন শেষ 20 পৃষ্ঠার।

এখন তারা মিলতে চায় এমন জোড়া যাদের নম্বর যোগ করলে ঠিক T হয়। একসাথে পুরো বই খুঁজলে কাজটা বিশাল; কিন্তু একজনের গোছানো (sorted) খাতা থাকলে অন্যজন তার প্রতিটা নম্বরের জন্য চট করে "এর জোড়া আছে কি?" দেখে নিতে পারে। দুই দিক থেকে আসা — তাই নাম meet in the middle (মাঝখানে দেখা)।

5. Visual explanation

পুরো array দুই অর্ধেকে ভাঙা, তারপর দুই দিকের subset-sum মিলিয়ে দেখা:

array = [1, 2, 3, 4],  T = 5

        ভাঙো মাঝখানে
   ┌──────────┐   ┌──────────┐
   │  1   2   │   │   3   4  │
   └──────────┘   └──────────┘
   বাঁ অর্ধেক          ডান অর্ধেক

বাঁ-এর সব subset-sum:  L = [0, 1, 2, 3]
ডান-এর সব subset-sum:  R = [0, 3, 4, 7]   (sorted)

প্রতিটা s (বাঁ) এর জন্য R-এ (T - s) খোঁজো:
   s = 0  ->  চাই 5  ->  R-এ নেই       ✗
   s = 1  ->  চাই 4  ->  R-এ আছে       ✓   ({1} + {4})
   s = 2  ->  চাই 3  ->  R-এ আছে       ✓   ({2} + {3})
   s = 3  ->  চাই 2  ->  R-এ নেই       ✗

মোট মিল = 2

লক্ষ করো — বাঁ-এর 4টা আর ডান-এর 4টা, মোটে 4 + 4 কাজ; পুরো 16টা subset ঘোরা লাগল না।

6. Example input and output

arr               T    output   ব্যাখ্যা
-----------------------------------------------------
[1, 2, 3, 4]      5    2        {1,4}, {2,3}
[1, 2, 3]         0    1        শুধু খালি subset {} এর যোগফল 0
[1, 2, 3]         6    1        {1,2,3}
[2, 2]            2    2        প্রথম {2}, দ্বিতীয় {2} — আলাদা subset
[1, 1, 1]         5    0        সর্বোচ্চ যোগফল 3, 5 অসম্ভব

দুটো edge case খেয়াল করো: খালি subset-ও একটা subset (যোগফল 0), আর একই মান দুবার থাকলে তারা আলাদা subset হিসেবে গোনা হয় (index আলাদা)।

7. Brute force thinking

সবচেয়ে সোজা ভাবনা: সব subset একে একে বানাও, প্রতিটার যোগফল মাপো, T-এর সাথে মেলে কিনা গোনো। Subset enumeration তো জানা (047) — bitmask দিয়ে:

def brute_count(arr, target):
    n = len(arr)
    count = 0
    for mask in range(1 << n):                 # সব 2^n subset
        s = sum(arr[i] for i in range(n) if mask >> i & 1)
        if s == target:
            count += 1
    return count

এটা একদম ঠিক উত্তর দেয় — [1,2,3,4], T=5 → 2। ছোট n-এ নিশ্চিন্তে চলে, আর আমাদের meet-in-the-middle-এর সঠিকতা যাচাইয়ের মাপকাঠি হিসেবেও কাজে লাগবে।

8. Why brute force may be slow

সমস্যা একটাই — loop ঘোরে 2^n বার। n বাড়লে এটা ভয়ংকর দ্রুত ফুলে ওঠে:

n = 20  ->  2^20  ≈ 10 লাখ          (ঠিক আছে)
n = 30  ->  2^30  ≈ 100 কোটি        (সীমান্তে)
n = 40  ->  2^40  ≈ 1,00,000 কোটি   (অসম্ভব — TLE)

প্রতিটা subset বানাতে আবার ভেতরে nটা bit পড়া — মোট O(2^n · n)। n = 40-এ এটা আক্ষরিক অর্থে অসম্ভব। অথচ এই n ≈ 40 মাপটাই meet in the middle-এর জন্য একদম মানানসই।

9. Better thinking

মূল insight: 2^40 বড়, কিন্তু 2^20 ছোট। তাই array-কে দুই অর্ধেকে ভাঙো — প্রতিটার subset মোটে 2^20 ≈ 10 লাখ।

  • বাঁ অর্ধেকের সব subset-sum-এর list L বানাও।
  • ডান অর্ধেকের সব subset-sum-এর list R বানাও, sort করো।
  • প্রতিটা s ∈ L-এর জন্য R-এ T − s কয়বার আছে গোনো (binary search দিয়ে — bisect_left থেকে bisect_right)।

প্রতিটা subset ঠিক একবার গোনা পড়বে: বাঁ অর্ধেকের অংশ s, ডান অর্ধেকের অংশ T − s — একসাথে পুরো subset। 2^40 নেমে এলো 2 · 2^20 · log(2^20) ≈ কয়েক কোটি কাজে।

10. Thinking tweak

এক লাইনের "আহা": পুরো brute force-টা একসাথে না চালিয়ে ঠিক মাঝখানে কাটো — তাহলে exponent অর্ধেক হয়ে যায়, আর দুই টুকরোকে sorted-match দিয়ে আবার জোড়া দেওয়া যায়।

গুরুত্বপূর্ণ ফাঁদ: ভাঙাটা সহজ, কিন্তু merge-এর খরচ ভুলে গেলে লাভ নেই। বাঁ-এর প্রতিটা s-এর জন্য ডান-এ যদি linear search করো, আবার O(2^(n/2) · 2^(n/2)) = O(2^n)-এ ফিরে যাবে! তাই ডান list sort করে binary search — এটাই আসল চাবি।

11. Step-by-step dry run

arr = [1, 2, 3, 4], T = 5 ধরে চালাই:

  1. ভাঙা: half = 2। বাঁ = [1, 2], ডান = [3, 4]।
  2. বাঁ subset-sum: subset গুলো {}=0, {1}=1, {2}=2, {1,2}=3 → L = [0, 1, 2, 3]।
  3. ডান subset-sum + sort: {}=0, {3}=3, {4}=4, {3,4}=7 → R = [0, 3, 4, 7]।
  4. match: count = 0 থেকে শুরু।
s (বাঁ) চাই T − s R-এ কয়বার? count
0 5 0 0
1 4 1 1
2 3 1 2
3 2 0 2
  1. শেষ: count = 2। ঠিক — {1,4} আর {2,3}।

12. Python solution

from bisect import bisect_left, bisect_right


def subset_sums(arr):
    """arr-এর প্রতিটা subset-এর যোগফলের list ফেরত দেয় (2^len বানায়)।"""
    sums = []
    n = len(arr)
    for mask in range(1 << n):              # 047-এর bitmask enumeration
        s = 0
        for i in range(n):
            if mask >> i & 1:               # i-তম element subset-এ আছে?
                s += arr[i]
        sums.append(s)
    return sums


def count_subsets_with_sum(arr, target):
    """arr-এর কয়টা subset-এর যোগফল ঠিক target — meet in the middle-এ।"""
    n = len(arr)
    half = n // 2
    left = subset_sums(arr[:half])
    right = sorted(subset_sums(arr[half:]))   # merge-এর জন্য sort জরুরি
    count = 0
    for s in left:
        # right-এ (target - s) কয়বার আছে = bisect_right - bisect_left
        lo = bisect_left(right, target - s)
        hi = bisect_right(right, target - s)
        count += hi - lo
    return count


def brute_count(arr, target):
    """ছোট case-এ মিলিয়ে দেখার জন্য সরল 2^n version।"""
    n = len(arr)
    c = 0
    for mask in range(1 << n):
        s = sum(arr[i] for i in range(n) if mask >> i & 1)
        if s == target:
            c += 1
    return c


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert count_subsets_with_sum([1, 2, 3, 4], 5) == 2     # {1,4}, {2,3}
assert count_subsets_with_sum([1, 2, 3], 0) == 1        # শুধু খালি subset
assert count_subsets_with_sum([1, 2, 3], 6) == 1        # {1,2,3}
assert count_subsets_with_sum([2, 2], 2) == 2           # দুটো আলাদা {2}
assert count_subsets_with_sum([1, 1, 1], 5) == 0        # অসম্ভব

# brute force-এর সাথে এলোমেলো case-এ মিলিয়ে দেখা (সঠিকতার প্রমাণ)
import random
for _ in range(500):
    k = random.randint(1, 9)
    a = [random.randint(0, 6) for _ in range(k)]
    t = random.randint(0, 25)
    assert count_subsets_with_sum(a, t) == brute_count(a, t), (a, t)

print(count_subsets_with_sum([1, 2, 3, 4], 5))   # 2
print(count_subsets_with_sum([1, 2, 3, 4, 5], 7))  # 3: {2,5},{3,4},{1,...}
print("সব test pass!")

13. Line-by-line explanation

def subset_sums(arr):
    for mask in range(1 << n):

1 << n মানে 2^n। প্রতিটা mask একটা subset-এর code — তার i-তম bit 1 হলে i-তম element subset-এ আছে। এটাই 047-এর subset enumeration।

        if mask >> i & 1:
            s += arr[i]

mask >> i & 1 দেখে i-তম bit জ্বলছে কিনা; জ্বললে সেই element যোগফলে যোগ করি। শেষে এই subset-এর যোগফল list-এ ঢোকে।

    half = n // 2
    left = subset_sums(arr[:half])
    right = sorted(subset_sums(arr[half:]))

Array-কে দুই ভাগে কাটছি। ডান অর্ধেকের sum-list sort করছি — কারণ এর উপরেই binary search চালাব। এই sort না করলে পুরো গতি ফিরে চলে যায় brute force-এ।

        lo = bisect_left(right, target - s)
        hi = bisect_right(right, target - s)
        count += hi - lo

বাঁ-এর প্রতিটা যোগফল s-এর জন্য ডানে চাই target − s। bisect_left দেয় সেই মানের প্রথম index, bisect_right দেয় শেষ মানের পরের index — তাদের পার্থক্যই বলে দেয় target − s ঠিক কয়বার আছে (duplicate গুনতে এটাই নিখুঁত)।

বাকি brute_count আর assert গুলো নিজেদের যাচাই করছে — random array-তে দুই পদ্ধতির উত্তর মেলে কিনা দেখে। সব মিললে শেষে সব test pass! ছাপে।

14. Output walkthrough

চালালে ছাপবে:

2
3
সব test pass!

প্রথম লাইন [1,2,3,4], T=5 → 2 ({1,4}, {2,3})। দ্বিতীয় লাইন [1,2,3,4,5], T=7 → 3 ({2,5}, {3,4}, {1,...} — নিজে গুনে মিলিয়ো)। তার আগের 500টা random assert চুপচাপ pass করেছে — মানে meet-in-the-middle আর brute force সবসময় একই উত্তর দিচ্ছে। সবশেষে সব test pass!।

15. Time complexity

O(2^(n/2) · n + 2^(n/2) · log(2^(n/2))) ≈ O(2^(n/2) · n)। দুই অর্ধেকের subset বানানো 2 · 2^(n/2), sort 2^(n/2) · (n/2), আর প্রতিটা বাঁ-sum-এর জন্য binary search log(2^(n/2)) = n/2। মূল কথা: exponent n থেকে n/2-এ নেমে এল — n = 40-এ 2^40 (অসম্ভব) থেকে 2^20 (লাখখানেক) — আকাশ-পাতাল।

16. Space complexity

O(2^(n/2)) — দুই অর্ধেকের subset-sum list দুটো মিলিয়ে। পুরো 2^n কখনো একসাথে রাখি না বলেই এটা সম্ভব; এটাই brute force-এর তুলনায় বড় সাশ্রয়।

17. Common mistakes

  1. Merge-এর খরচ ভুলে যাওয়া — ডান list sort না করে linear search করলে আবার O(2^n); sort + binary search না হলে পুরো লাভ মাটি (concept-notes-এর common mistake #1)।
  2. খালি subset বাদ দেওয়া — mask = 0-ও একটা subset (যোগফল 0); T = 0-এর উত্তর তাই অন্তত 1।
  3. Duplicate ঠিকমতো না গোনা — T − s একাধিকবার থাকলে bisect_right − bisect_left দিয়ে গোনা; শুধু "আছে কিনা" দেখলে গণনা ভুল।
  4. অসম ভাঙা সমস্যা ভাবা — n বিজোড় হলে n//2 আর n − n//2 আলাদা; এতে কোনো ক্ষতি নেই, দুই অর্ধেক আলাদা মাপের হলেও কৌশল ঠিকঠাক চলে।
  5. n ছোট হলেও MITM চালানো — n ≤ 20-এ সোজা brute force-ই সহজ ও যথেষ্ট; MITM-এর জটিলতা তখন অকারণ।

18. Harder problems that inherit this idea

19. Pattern learned

Split + merge (meet in the middle) — যখন brute force 2^n সামান্য বড় (n ≈ 34–42) আর "সব subset দেখতে হবে" গন্ধ, তখন array-কে অর্ধেকে ভেঙে দুই দিকের ফল sorted-match করো। Exponent অর্ধেক হয়, কিন্তু merge অবশ্যই binary search/two-pointer দিয়ে।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "n ≈ 40 + subset দেখলেই meet in the middle — মাঝখানে ভেঙে দুই অর্ধেকের subset-sum বানাও, একটাকে sort করো, প্রতিটা s-এর জোড়া T − s binary search-এ খোঁজো। merge sort না করলে লাভ নেই।"

পরের ধাপ → 140 — Ternary Search (search-ঘরানার আরেকটা: পাহাড়ের চূড়া খোঁজা)। শিকড় → 047 / 062 — subset / bitmask enumeration।

ফিরে দেখা: এই level-এর map → ../README.md · চিন্তার ছাঁচ → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "CP-style pattern" / "common interview pattern" বলা হয়েছে।