Problem link ও উৎস
- **Original source:** Classic 0/1 subset-sum (boolean) exercise
- **Platform:** LeetCode —
- **Topic:** dynamic programming
- **Difficulty:** Medium
- **Pattern:** Subset-sum (0/1, boolean)
- **Basic idea inherited from:** Knapsack skeleton — "প্রতিটা item নাও বা বাদ দাও," কিন্তু value-র বদলে boolean reachability
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা positive integer-এর array `nums` দেওয়া। প্রশ্ন: array-টাকে কি **দুটো ভাগে** এমনভাবে ভাঙা যায় যাতে দুই ভাগের যোগফল সমান হয়? শুধু "হ্যাঁ/না" (boolean) বলতে হবে। সমান দুই ভাগ মানে প্রতিটা ভাগের sum = মোট sum-এর অর্ধেক — তাই আসল প্রশ্ন হয়ে দাঁড়ায়: "এমন কোনো subset আছে কি যার sum ঠিক `total / 2`?"
```text
nums = [1, 5, 11, 5]
মোট = 22, অর্ধেক = 11
subset {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 (মোট 11, বিজোড়)
Input : nums = [1,1] -> Output: True ({1} ও {1})
Edge case 1: nums = [1] -> Output: False (মোট 1, বিজোড়)
Edge case 2: nums = [2,2,2,2] -> Output: True ({2,2} ও {2,2})
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তোমার কাছে কিছু ওজনের বাটখারা, আর তুমি দুই পাল্লার দাঁড়িপাল্লা ঠিক balance করতে চাও। মোট ওজন বিজোড় হলে কখনো balance হবে না। নয়তো এক পাল্লায় ঠিক অর্ধেক ওজন তুলতে হবে। প্রতিটা বাটখারার সামনে সিদ্ধান্ত: "এটা বাঁ পাল্লায় রাখব, না রাখব না?" — যদি কোনো বাছাইয়ে বাঁ পাল্লা ঠিক অর্ধেকে দাঁড়ায়, balance সম্ভব।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি **0/1 knapsack-এর কঙ্কাল**: প্রতিটা item-এ একটা binary সিদ্ধান্ত — নাও বা বাদ দাও, আর প্রতিটা item সর্বোচ্চ একবার। তফাত: knapsack value maximize করে, এখানে আমরা শুধু জানতে চাই একটা নির্দিষ্ট sum **পৌঁছানো যায় কি না** (boolean reachability)। তাই `dp` value নয়, `True/False` ধরে। "একবারই নেওয়া যায়" নিয়মটা loop-direction (right-to-left) দিয়ে enforce হয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুই ধাপ। (১) মোট sum **বিজোড়** হলে সমান দুই ভাগ অসম্ভব — সঙ্গে সঙ্গে False। (২) নয়তো `target = total / 2` ঠিক করে জিজ্ঞেস করো: কিছু item বেছে ঠিক `target` বানানো যায় কি? প্রতিটা item-এ সিদ্ধান্ত — এটা subset-এ নিলে দরকার কমে `target - nums[i]`, না নিলে `target` অপরিবর্তিত। যেকোনো একটা পথ `target == 0`-এ পৌঁছালেই True।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **1D boolean array** `dp` (size `target + 1`), `dp[s]` = এখন পর্যন্ত দেখা item দিয়ে sum `s` বানানো সম্ভব কি না। Top-down করলে একটা **dict** (state `(i, rem)` → bool)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State: কোন item পর্যন্ত বিবেচনা করেছি, আর কত sum বানাতে বাকি। 1D-তে compress করলে শুধু "sum `s` reachable কি না" রাখি, কারণ item একে একে process করার সময় আগের item-এর reachable sum-গুলোই দরকার। boolean যথেষ্ট — আমরা *পরিমাণ* নয়, *সম্ভাব্যতা* track করছি। 0/1 নিশ্চিত করতে inner loop **right-to-left**, যাতে প্রতিটা item একবারই গোনা হয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা item-এ recurse করে দুটো শাখা — এই item subset-এ নাও (target কমাও), বা বাদ দাও।
```text
can(i, rem): # item i থেকে শুরু করে rem বানানো যায়?
if rem == 0: return True
if i == n or rem < 0: return False
return can(i+1, rem - nums[i]) # নাও
or can(i+1, rem) # বাদ দাও
answer = can(0, total // 2) (total বিজোড় হলে সরাসরি False)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই recursion **O(2^n)** — প্রতিটা item-এ দুটো শাখা, মোট সব subset (2^n)। একই `(i, rem)` জোড়া বহু পথ দিয়ে বারবার পৌঁছানো হয় (overlapping subproblems)। 30+ item হলেই subset-সংখ্যা বিস্ফোরিত হয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **distinct state মাত্র `n × target`-টা** (`(i, rem)` জোড়া)। প্রতিটার উত্তর একবার গুনে রাখলে exponential subset-search polynomial (pseudo-polynomial, O(n × target)) হয়ে যায়। 1D-তে এটা আরও ছোট: শুধু কোন sum reachable তা track করি।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[s]` = এখন পর্যন্ত process করা item-গুলোর কোনো subset দিয়ে ঠিক sum `s` বানানো সম্ভব কি না (boolean)। (Top-down-এ: `can(i, rem)` = item `i..n-1` থেকে `rem` বানানো যায় কি না।)
**Transition:**
```text
নতুন item x-এর জন্য (1D, right-to-left):
dp[s] = dp[s] or dp[s - x] for s = target down to x
```
কারণ: sum `s` হয় `x` ছাড়াই reachable ছিল (`dp[s]`), নয় `x` যোগ করে `s - x` থেকে (`dp[s-x]`)।
**Base case:** `dp[0] = True` (খালি subset দিয়ে sum 0 সবসময় সম্ভব)। আগে check: `total` বিজোড় হলে সরাসরি False।
**Answer location:** `dp[target]`, যেখানে `target = total // 2`।
Memoization (top-down): উপরের `can(i, rem)` recursion, dict যোগ। Tabulation (bottom-up): প্রতিটা item নিয়ে inner loop ডান-থেকে-বাঁ — **এই direction-ই 0/1 নিশ্চিত করে** (প্রতিটা item একবার)। বাঁ-থেকে-ডান করলে নিঃশব্দে unbounded হয়ে যেত।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "দুই ভাগে ভাঙব" — এই দ্বি-পক্ষীয় চিন্তা বাদ দিয়ে এক-পক্ষীয় করো: "একটা ভাগের sum যদি `total/2` হয়, বাকিটা এমনিই `total/2`।" তাই দুই-ভাগ problem একটা **single subset-sum reachability** problem-এ পরিণত হয়। আর knapsack-এর সবচেয়ে কুখ্যাত নিয়ম এখানেই শিখি: **0/1 = inner loop ডান-থেকে-বাঁ**।
### ছবিতে বোঝা {#7-visual-explanation}
`dp[s]` = sum `s` reachable কি না (T/F)। `nums = [1, 5, 11, 5]`, `target = 11`:
```text
শুরুতে: dp[0]=T, বাকি সব F
item 1 (=1): reachable sums: {0, 1}
item 2 (=5): {0, 1, 5, 6}
item 3 (=11): {0, 1, 5, 6, 11} <- 11 পৌঁছে গেছে!
item 4 (=5): {0, 1, 5, 6, 10, 11, 16->skip>11}
প্রতিটা নতুন item x-এ, ডান-থেকে-বাঁ:
for s from target down to x:
dp[s] = dp[s] or dp[s - x]
s=11 হয়ে গেছে T -> answer True
```
ডান-থেকে-বাঁ যাওয়াটা জরুরি: একই item দুবার গোনা আটকায় (0/1)। বাঁ-থেকে-ডান গেলে একই item বহুবার ব্যবহৃত হয়ে যেত (unbounded)।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`nums = [2, 2, 2, 2]`, `total = 8`, `target = 4`, 1D tabulation:
1. `dp = [T, F, F, F, F]` (dp[0]=T)
2. item 2: s=4→dp[2]? F; s=3→dp[1]? F; s=2→dp[0]=T → dp[2]=T → `dp=[T,F,T,F,F]`
3. item 2: s=4→dp[2]=T → dp[4]=T; s=2→dp[0]=T (already) → `dp=[T,F,T,F,T]`
4. item 2, item 2: dp[4] already T, কিছু বদলায় না
5. return `dp[4] = True`
হাতে মিলিয়ে: {2,2} আর {2,2} — দুই ভাগ সমান। ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
# ---- way 1: memoization (top-down) ----
def can_partition_memo(nums):
total = sum(nums)
if total % 2 != 0: # বিজোড় হলে অসম্ভব
return False
target = total // 2
n = len(nums)
memo = {}
def can(i, rem): # item i..n-1 থেকে rem বানানো যায়?
if rem == 0:
return True
if i == n or rem < 0:
return False
if (i, rem) in memo:
return memo[(i, rem)]
memo[(i, rem)] = can(i + 1, rem - nums[i]) or can(i + 1, rem)
return memo[(i, rem)]
return can(0, target)
# ---- way 2: tabulation (bottom-up, 1D, right-to-left = 0/1) ----
def can_partition_tab(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True # খালি subset
for x in nums:
for s in range(target, x - 1, -1): # ডান-থেকে-বাঁ -> প্রতিটা item একবার
if dp[s - x]:
dp[s] = True
return dp[target]
# ---- tests ----
cases = [
([1, 5, 11, 5], True),
([1, 2, 3, 5], False),
([1, 1], True),
([1], False),
([2, 2, 2, 2], True),
([100], False),
([3, 3, 3, 4, 5], True), # total 18, target 9: 4+5 বা 3+3+3
([1, 2, 5], False), # total 8, target 4: পৌঁছানো যায় না
]
for nums, want in cases:
assert can_partition_memo(nums) == want, (nums, can_partition_memo(nums))
assert can_partition_tab(nums) == want, (nums, can_partition_tab(nums))
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `can_partition_memo`: আগে বিজোড়-sum check; `can(i, rem)` item `i` থেকে শুরু করে `rem` বানানো যায় কি না; `rem==0` → True, শেষ/negative → False; `memo` repeated কাজ এড়ায়।
- `can_partition_tab`: `dp[0]=True`; প্রতিটা item-এ inner loop **ডান-থেকে-বাঁ** — এতেই 0/1 (একবার নেওয়া) নিশ্চিত হয়; `dp[s] = dp[s] or dp[s-x]`; answer `dp[target]`।
- দুই function-ই বিজোড় মোট sum-এ সরাসরি False দেয় (অর্ধেক integer হয় না)।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ আটটা input — LeetCode-এর `True`/`False` জোড়া, সহজ `[1,1] True`, single-element `[1] False`, all-equal `[2,2,2,2] True`, একটা বড় `[3,3,3,4,5] True` (দুই রকম partition), আর একটা সম-মোট কিন্তু unreachable `[1,2,5] False`। প্রতিটার জন্য দুই function-ই মিলতে হবে। সব pass হলে শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
Subset-sum reachability `total/2`; 1D boolean, inner loop **ডান-থেকে-বাঁ** (0/1)। বিজোড় হলে সরাসরি false।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// dp[s] = sum s reachable কি না; ডান-থেকে-বাঁ -> প্রতিটা item একবার
function canPartition(nums) {
const total = nums.reduce((a, b) => a + b, 0);
if (total % 2 !== 0) return false; // বিজোড় -> অসম্ভব
const target = total / 2;
const dp = new Array(target + 1).fill(false);
dp[0] = true; // খালি subset
for (const x of nums) {
for (let s = target; s >= x; s--) { // ডান-থেকে-বাঁ
if (dp[s - x]) dp[s] = true;
}
}
return dp[target];
}
// ---- test cases (example + edge) ----
const cases = [
[[1, 5, 11, 5], true],
[[1, 2, 3, 5], false], // মোট 11, বিজোড়
[[1, 1], true],
[[1], false], // single, বিজোড়
[[2, 2, 2, 2], true],
[[100], false],
[[3, 3, 3, 4, 5], true], // target 9: 4+5 বা 3+3+3
[[1, 2, 5], false], // সম-মোট কিন্তু unreachable
];
for (const [nums, want] of cases) {
assert(canPartition(nums) === want, "part " + nums);
}
console.log("সব JS test pass!");
```
> **JS টীকা:** 0/1 নিশ্চিত করতে inner loop **`s = target` থেকে `x` পর্যন্ত নিচে** (`s--`) — বাঁ-থেকে-ডান করলে একই item বহুবার গোনা হয়ে ভুল `true` আসতে পারে। মোট sum বের করতে `nums.reduce((a,b)=>a+b, 0)` (initial value `0` দাও, খালি array-তে নিরাপদ)। `new Array(n).fill(false)` boolean primitive বলে নিরাপদ; বিজোড় sum আগে check করলে `target` integer থাকে।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function canPartition(nums: number[]): boolean {
const total: number = nums.reduce((a, b) => a + b, 0);
if (total % 2 !== 0) return false;
const target: number = total / 2;
const dp: boolean[] = new Array(target + 1).fill(false);
dp[0] = true;
for (const x of nums) {
for (let s = target; s >= x; s--) {
if (dp[s - x]) dp[s] = true;
}
}
return dp[target];
}
function expect