Problem link ও উৎস
- **Original source:** Classic cross-topic capstone interview problem (subset-sum / 0-1 knapsack family)
- **Platform:** LeetCode —
- **Topic:** dynamic programming + math
- **Difficulty:** Medium
- **Pattern:** Subset-sum DP (0-1 knapsack, boolean reachability)
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **12 dynamic programming** (কোন কোন sum বানানো সম্ভব, তার একটা boolean table) আর **01 math** (sum-এর parity দিয়ে আগে থেকেই অসম্ভব case ছেঁটে ফেলা)। দুই tool জোড়া লাগলেই subset-sum।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা positive integer-এর array দেওয়া আছে। তোমার কাজ: বলো এটাকে **দুই ভাগে** ভাগ করা যায় কিনা, যাতে দুই ভাগের **যোগফল সমান** হয়। প্রতিটা সংখ্যা ঠিক একটা ভাগে যাবে। শুধু `True`/`False` চাই।
```text
nums : [1, 5, 11, 5]
ভাগ : {11} আর {1, 5, 5} -> দুটোরই sum = 11 -> True
```
### Input ও output {#8-example-input-and-output}
```text
Input : nums = [1, 5, 11, 5] -> Output: True # {11} আর {1,5,5}
Input : nums = [1, 2, 3, 5] -> Output: False # total=11 (odd) -> অসম্ভব
Edge case 1 (দুটো সমান): nums = [1, 1] -> Output: True # {1} আর {1}
Edge case 2 (একটা সংখ্যা): nums = [1] -> Output: False # ভাগ করার মতো কিছু নেই
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তোমার কিছু আলাদা ওজনের বাটখারা আছে, আর তুমি দু'পাল্লার দাঁড়িপাল্লা ঠিক ভারসাম্যে আনতে চাও। আগে মোট ওজন মাপো — বিজোড় হলে সমান দু'ভাগ অসম্ভব, চেষ্টাই করো না (এটাই parity-shortcut)। জোড় হলে তুমি কেবল দেখতে চাও: কিছু বাটখারা বেছে এক পাল্লায় ঠিক "অর্ধেক ওজন" তোলা যায় কিনা — পারলেই বাকিগুলো অন্য পাল্লায় সমান হবে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **12 dynamic programming** থেকে: "কোন কোন subset-sum বানানো সম্ভব" — `0` থেকে `target` পর্যন্ত প্রতিটা sum-এর জন্য একটা boolean reachability state রাখা (0-1 knapsack-এর রূপ)।
- **01 math** থেকে: একটা সহজ সংখ্যাতাত্ত্বিক pruning — **মোট sum যদি odd হয়, সমান দু'ভাগ অসম্ভব** (অর্ধেক integer হবে না)। তাই DP শুরুর আগেই অর্ধেক case বাদ।
একা DP তোমাকে দেয় সব subset না ঘুরে "কোন sum সম্ভব" জানার ক্ষমতা; একা math দেয় শুরুতেই অসম্ভব case ছাঁটার ক্ষমতা। দুটো মিললে O(n × target)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
প্রথম math: যদি দুই ভাগ সমান হয়, প্রতিটার sum হবে `total / 2`। তাই **`total` odd হলেই উত্তর `False`** — কোনো subset-ই অর্ধেক বানাতে পারবে না। `total` even হলে problem-টা দাঁড়ায়: "এমন একটা subset আছে কি, যার sum ঠিক `target = total / 2`?" — কারণ সেই subset পেলে বাকিরাও আপনা থেকেই `target` হবে।
লুকানো DP logic একটা **reachability**: `dp[s]` = "এ পর্যন্ত দেখা সংখ্যা দিয়ে ঠিক `s` sum বানানো সম্ভব কি?" প্রতিটা নতুন `num`-এ, আগে যত sum সম্ভব ছিল, তাদের প্রতিটার সাথে `num` যোগ করেও নতুন sum সম্ভব হয়:
```text
dp[s] হয়ে যায় True যদি dp[s - num] আগে True থাকে
```
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **1D boolean array `dp`**, length `target + 1`। `dp[s]` ধরে রাখে "`s` বানানো যায় কিনা"। এটাই 12 DP-র knapsack table; 01 math শুধু target নির্ধারণ আর parity-ছাঁটে সাহায্য করে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
আমাদের জানতে হবে শুধু "অমুক sum কি reachable" — হ্যাঁ/না। তাই পুরো subset store করার দরকার নেই, প্রতিটা সম্ভাব্য sum-এর জন্য একটা **boolean** (12 DP) যথেষ্ট। sum-গুলো `0..target` পর্যন্ত ছোট ও পরপর integer, তাই array-ই নিখুঁত — O(1) index। আর target নিজে `total/2`, যা math (01) দেয়; total odd হলে array বানানোর আগেই বেরিয়ে যাই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা সংখ্যার জন্য দুটো পছন্দ — subset-এ নাও বা নিও না। সব combination ঘুরে দেখো কোনোটার sum `target` হয় কিনা।
```text
def can(i, s):
if s == target: return True
if i == n or s > target: return False
return can(i+1, s + nums[i]) or can(i+1, s) # নাও / নিও না
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা element-এ দুটো branch — মোট **O(2^n)** combination। memo ছাড়া একই `(i, s)` জোড়া বহুবার ফিরে আসে। যেমন আলাদা পথে একই running sum তৈরি হয়, প্রতিবার নতুন করে গণনা হয়। এই পুনরাবৃত্তিই 12 DP দূর করে — `0..target` প্রতিটা sum মাত্র একবার "reachable কিনা" হিসাব করে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
দুটো observation একসাথে: (১) **math** — total odd হলে উত্তর সাথে সাথে `False`, কোনো কাজ লাগে না। (২) **DP** — কোন কোন sum reachable, তা subset কোন order-এ বাছছ তার উপর নির্ভর করে না; শুধু "এ পর্যন্ত কোন sums বানানো যায়" — এই boolean set-টাই যথেষ্ট, প্রকৃত subset লাগে না। এই দুই observation মিলে exponential search-টাকে O(n × target)-এ নামায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
আগে `total` বের করো; odd হলে `False`। নাহলে `target = total // 2`। একটা boolean `dp` নাও, `dp[0] = True`। প্রতিটা `num`-এর জন্য sum-গুলো **উঁচু থেকে নিচু** (`target` → `num`) scan করে `dp[s]`-কে `dp[s] or dp[s - num]` করো — উঁচু-থেকে-নিচু order একটা `num` দুবার ব্যবহার হওয়া আটকায় (0-1 knapsack, প্রতিটা একবার)। শেষে `dp[target]`-ই উত্তর।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "দুই ভাগে কীভাবে ভাঙব" ভাবার বদলে ভাবো "মোটের ঠিক অর্ধেক sum-এর একটা subset আছে কি?" — একটা ভাগ পেলেই বাকিটা free। আর "কোন কোন subset" নয়, শুধু "কোন কোন **sum** reachable" — এই boolean-এ নামালেই exponential চলে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [1, 5, 11, 5]`, `total = 22`, `target = 11`। `dp` (reachable sums) বদলায়:
```text
শুরু: dp[0]=T, বাকি সব F (শূন্য sum সবসময় সম্ভব)
num=1: s=1 <- dp[0] reachable: {0,1}
num=5: s=6 <-dp[1], s=5 <-dp[0] reachable: {0,1,5,6}
num=11: শুধু s=11 <- dp[0] update reachable: {0,1,5,6,11}
11-এর বড় sum table-এ নেই; target=11 পর্যন্তই রাখি।
-> dp[11] = True! (শুধু {11} দিয়েই)
num=5: descending update শেষে reachable: {0,1,5,6,10,11}
dp[11] = True থাকে; 1+5+5 দিয়েও 11 হয়।
dp[target=11] = True -> উত্তর True
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`nums = [1, 5, 5]`, `total = 11` (odd) → সরাসরি `False`। এবার একটা even case `nums = [2, 2, 1, 1]`, `total = 6`, `target = 3`:
1. শুরু: `dp = [T, F, F, F]` (index 0..3)
2. `num=2`: `s=3 <- dp[1]?F`; `s=2 <- dp[0]?T` → `dp[2]=T`। now `{0,2}`
3. `num=2`: `s=3 <- dp[1]?F`; `s=2 <- dp[0]?T` (already)। now `{0,2}`
4. `num=1`: `s=3 <- dp[2]?T` → `dp[3]=T`; `s=1 <- dp[0]?T` → `dp[1]=T`। now `{0,1,2,3}`
5. `dp[target=3] = True` → return `True` (যেমন `{2,1}`)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def can_partition(nums):
total = sum(nums)
if total % 2 != 0: # 01 math: odd মোট -> সমান দু'ভাগ অসম্ভব
return False
target = total // 2
dp = [False] * (target + 1) # dp[s] = s বানানো সম্ভব?
dp[0] = True # শূন্য sum সবসময় সম্ভব
for num in nums:
for s in range(target, num - 1, -1): # উঁচু->নিচু: প্রতিটা num একবার
if dp[s - num]:
dp[s] = True
return dp[target]
# ---- tests ----
assert can_partition([1, 5, 11, 5]) == True # {11} | {1,5,5}
assert can_partition([1, 2, 3, 5]) == False # total 11 (odd)
assert can_partition([1, 1]) == True # {1} | {1}
assert can_partition([2, 2, 1, 1]) == True # {2,1} | {2,1}
assert can_partition([1]) == False # ভাগ করার মতো নেই
assert can_partition([3, 3, 3, 4, 5]) == True # {3,3,3} | {4,5} = 9
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `total = sum(nums)` — পুরো array-র যোগফল; অর্ধেকটাই হবে target।
- `if total % 2 != 0: return False` — 01 math-এর parity shortcut; odd হলে আর কিছু করার নেই।
- `target = total // 2` — একটা subset-কে ঠিক এতটুকু sum বানাতে হবে।
- `dp = [False] * (target + 1)` — সব sum শুরুতে unreachable।
- `dp[0] = True` — কিছু না নিয়েই sum 0 বানানো যায় (base case)।
- `for num in nums` — প্রতিটা সংখ্যা একবার বিবেচনা (0-1 knapsack-এর item loop)।
- `for s in range(target, num - 1, -1)` — sum উঁচু থেকে নিচু; এই উল্টো order একই `num`-কে দুবার যোগ হওয়া আটকায় (প্রতিটা item একবার)।
- `if dp[s - num]: dp[s] = True` — আগে `s - num` reachable হলে এখন `num` যোগ করে `s`-ও reachable।
- `return dp[target]` — অর্ধেক sum বানানো গেল কিনা — সেটাই উত্তর।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,5,11,5]`-এ `total=22` even, `target=11`। `num=11` প্রক্রিয়া করার সময় `dp[11]` `dp[0]` (True) থেকে True হয়ে যায় — অর্থাৎ শুধু `{11}` দিয়েই অর্ধেক, return True, assert pass। `[1,2,3,5]`-এ `total=11` odd, প্রথম লাইনেই return False। `[1]`-এ `total=1` odd → False। even-case গুলোতে DP `dp[target]` ঠিকভাবে True/False দেয়। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n × target)** — প্রতিটা সংখ্যা (`n`-টা) প্রতিবার `0..target` sum range scan করে। `target = total/2`, তাই pseudo-polynomial (মানের উপর নির্ভর)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(target)** — একটা মাত্র 1D boolean array, length `target + 1`। 2D table-ও সম্ভব, কিন্তু এক-সারির rolling form (উঁচু→নিচু loop) দিয়ে শুধু এক row রাখলেই চলে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- parity-check বাদ দেওয়া — odd total-এ অযথা DP চালানো (ভুল না, কিন্তু `target = total//2` floor-এ ভুল উত্তরও দিতে পারে)।
- inner loop **নিচু থেকে উঁচু** চালানো — তখন একই `num` একাধিকবার যোগ হয়ে যায়, এটা unbounded knapsack হয়ে যায়, 0-1 না; উঁচু→নিচু-ই ঠিক।
- `dp[0] = True` সেট না করা — base ছাড়া কোনো sum-ই reachable হবে না।
- target-কে `total / 2` (float) রাখা — integer `total // 2` ব্যবহার করো, নাহলে index ভাঙবে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: কোন কোন sum reachable, তার boolean DP table (12 DP-র [../../12-dynamic-programming/patterns.md](../../12-dynamic-programming/patterns.md), 0-1 knapsack family) + parity/divisibility দিয়ে আগেই অসম্ভব case ছাঁটা (01 math-এর [../../01-math-based-programming-fundamentals/](../../01-math-based-programming-fundamentals/README.md))। এই দুটো cold অবস্থায় জানা থাকলে subset-sum নিজে থেকেই দাঁড়িয়ে যায়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Target Sum (প্রতিটা সংখ্যার আগে +/- বসিয়ে target — একই subset-sum, কিন্তু count চায়) —