Problem link ও উৎস
- **Original source:** CSES Problem Set — Meet in the Middle (classic subset-sum split technique)
- **Platform:** CSES —
- **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/`)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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-এ যেতে পারো; পরে ফিরে এলে বেশি মজা পাবে।
### Input ও output {#6-example-input-and-output}
```text
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 আলাদা)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো দুই বন্ধু একটা বড় ধাঁধার বই অর্ধেক-অর্ধেক ভাগ করে নিলে। একজন প্রথম 20 পৃষ্ঠার সব সম্ভাব্য উত্তর-নম্বর একটা খাতায় লিখে গুছিয়ে রাখল; আরেকজন শেষ 20 পৃষ্ঠার।
এখন তারা মিলতে চায় এমন জোড়া যাদের নম্বর যোগ করলে ঠিক `T` হয়। একসাথে পুরো বই খুঁজলে কাজটা বিশাল; কিন্তু একজনের গোছানো (sorted) খাতা থাকলে অন্যজন তার প্রতিটা নম্বরের জন্য চট করে "এর জোড়া আছে কি?" দেখে নিতে পারে। দুই দিক থেকে আসা — তাই নাম **meet in the middle** (মাঝখানে দেখা)।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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।
### ভেতরের অঙ্ক {#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` খুঁজলেই হলো।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সোজা ভাবনা: সব subset একে একে বানাও, প্রতিটার যোগফল মাপো, `T`-এর সাথে মেলে কিনা গোনো। Subset enumeration তো জানা (047) — bitmask দিয়ে:
```python
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` বাড়লে এটা ভয়ংকর দ্রুত ফুলে ওঠে:
```text
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 — এটাই আসল চাবি।
### ছবিতে বোঝা {#5-visual-explanation}
পুরো array দুই অর্ধেকে ভাঙা, তারপর দুই দিকের subset-sum মিলিয়ে দেখা:
```text
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 ঘোরা লাগল না।
### ছোট input-এ ধাপে ধাপে {#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 |
5. **শেষ:** count = **2**। ঠিক — `{1,4}` আর `{2,3}`।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
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।
```text
if mask >> i & 1:
s += arr[i]
```
`mask >> i & 1` দেখে i-তম bit জ্বলছে কিনা; জ্বললে সেই element যোগফলে যোগ করি। শেষে এই subset-এর যোগফল list-এ ঢোকে।
```text
half = n // 2
left = subset_sums(arr[:half])
right = sorted(subset_sums(arr[half:]))
```
Array-কে দুই ভাগে কাটছি। ডান অর্ধেকের sum-list **sort** করছি — কারণ এর উপরেই binary search চালাব। এই sort না করলে পুরো গতি ফিরে চলে যায় brute force-এ।
```text
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!` ছাপে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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-এর জটিলতা তখন অকারণ।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Meet in the Middle** (