Problem link ও উৎস
- **Original source:** Classic backtracking exercise (power set)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (include-exclude branch)
- **Difficulty:** Medium
- **Pattern:** include/exclude branch — প্রতিটা item নাও বা বাদ দাও (2^n)
- **Basic idea inherited from:** decrease-and-conquer, এবার branching সহ
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যার list `nums` দেওয়া আছে (সব আলাদা)। তোমার কাজ: এর **সব subset** (power set) বের করা — মানে যত রকমভাবে কিছু element বেছে নেওয়া যায়, প্রতিটা সংগ্রহ। খালি subset `[]` আর পুরো list দুটোই গোনা। `n`টা element-এর জন্য মোট `2^n`টা subset।
```text
nums = [1, 2, 3]
subsets = [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] (মোট 8 = 2^3)
```
### Input ও output {#8-example-input-and-output}
```text
Input : [1, 2, 3] -> Output: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]
Input : [0] -> Output: [], [0]
Edge case 1 (খালি): [] -> Output: [[]] (শুধু খালি subset, মোট 1টা)
Edge case 2 (একটা): [9] -> Output: [], [9]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা পিৎজার toppings মেনু ভাবো: পনির, মাশরুম, লঙ্কা। প্রতিটা topping-এর জন্য তুমি হয় "হ্যাঁ দাও" নয় "না থাক" বলো। সব সম্ভাব্য পিৎজা = প্রতিটা topping-এ হ্যাঁ/না-এর সব সংমিশ্রণ — কিছুই না দেওয়া (plain) থেকে সব দেওয়া (deluxe) পর্যন্ত। প্রতিটা item-এ স্বাধীন দুটো choice-ই সব subset তৈরি করে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **decrease-and-conquer, এবার branching সহ**। আগের problem-গুলোতে প্রতিটা item-এ একটা করে recursive call হতো (একটা লাইন)। এখানে প্রতিটা item-এ **দুটো** call — একটায় item-টা নাও (include), একটায় বাদ দাও (exclude)। এই branching call-এর লাইনটাকে call-এর tree বানিয়ে দেয়, আর leaf-গুলোই subset।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো math হলো **rule of product**: প্রতিটা item-এর জন্য 2টা স্বাধীন choice (নাও / বাদ দাও), `n`টা item, তাই মোট `2 × 2 × ... × 2 = 2^n` সংমিশ্রণ। প্রতিটা subset আসলে একটা binary string — কোন কোন item আছে (1) আর কোনগুলো নেই (0)। এই tree-র প্রতিটা leaf একটা স্বতন্ত্র subset।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **list `path`** (বর্তমান subset গড়তে, shared/mutable) আর একটা **list `out`** (সব subset জমাতে)। recursion-এর জন্য **call stack**। backtracking-এর জন্য `path`-এ append/pop করি, আর record করার সময় `path[:]` snapshot রাখি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
একটা mutable list `path` দিয়ে আমরা পুরো decision-tree জুড়ে একটাই working subset বহন করি — include-এ append, ফিরে এসে pop (un-choose)। list-এর শেষে append/pop O(1), তাই প্রতিটা branch সস্তায় গড়া/ভাঙা যায়। আর record করার সময় `path[:]` copy না নিলে পরের পরিবর্তন আগের snapshot-কেও বদলে দিত — তাই snapshot জরুরি।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: 0 থেকে `2^n - 1` পর্যন্ত প্রতিটা সংখ্যাকে একটা bitmask ধরে নাও; যে bit 1, সেই index-এর element subset-এ ঢোকাও।
```text
for mask in range(2**n):
subset = [nums[i] for i in range(n) if mask & (1 << i)]
out.append(subset)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই bitmask version আসলে ঠিকঠাক **O(n · 2^n)** — খারাপ নয়, output-ই তো 2^n। মূল সীমাবদ্ধতা সময় নয়, **নমনীয়তা**: bitmask দিয়ে pruning করা বা duplicate skip করা (Subsets II) কঠিন। recursive include/exclude version-টা একই complexity-তে চলে কিন্তু সহজে বাড়ানো যায় — pruning, ordering, constraint যোগ করা যায়। তাই backtracking framework-টাই শেখার আসল লক্ষ্য।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **subset গড়া = প্রতিটা item-এ একটা স্বাধীন yes/no সিদ্ধান্ত**। "কোন কোন subset আছে?" না ভেবে ভাবো "এই একটা item নিয়ে আমার option কী?" — locally মাত্র দুটো option, কিন্তু সব level মিলে globally সব subset বেরিয়ে আসে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
index `i` ধরে হাঁটো। base case: `i == n` হলে বর্তমান `path`-এর একটা snapshot record করো। নাহলে দুটো branch: (1) `nums[i]` append করে `go(i+1)` — include; ফিরে এসে pop; (2) `go(i+1)` — exclude। প্রতিটা leaf-এ একটা সম্পূর্ণ subset। choose → explore → un-choose-এর নিখুঁত প্রয়োগ; `path` একটাই, leak শূন্য।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** পুরো power set একসাথে কল্পনা না করে শুধু **একটা item-এর সিদ্ধান্ত** দেখো — নেব না নেব না। recursion বাকি সব item-এর সব সংমিশ্রণ এমনিতেই খুলে দেবে। বিশাল 2^n সমস্যাটা একটা ছোট, দুই-শাখার সিদ্ধান্তে নেমে আসে।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতি index-এ দুটো branch — left = include, right = exclude। `[1, 2]`-এর decision tree:
```text
go(0, [])
include 1 / \ exclude 1
go(1,[1]) go(1,[])
inc 2 / \ exc 2 inc 2 / \ exc 2
go(2,[1,2]) go(2,[1]) go(2,[2]) go(2,[])
| | | |
record[1,2] record[1] record[2] record[]
leaf (index == n) = 4 = 2^2 subset। [1,2,3]-এ 8টা leaf।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`subsets([1, 2])`, `go(i, path)`:
1. `go(0,[])` → include 1: `path=[1]`, `go(1,[1])`।
2. `go(1,[1])` → include 2: `path=[1,2]`, `go(2,[1,2])`: `i==2` → record `[1,2]`; pop → `[1]`।
3. `go(1,[1])` → exclude 2: `go(2,[1])`: record `[1]`; ফিরে pop 1 → `[]`।
4. `go(0,[])` → exclude 1: `go(1,[])` → include 2: record `[2]`, pop; exclude 2: record `[]`।
5. out = `[[1,2],[1],[2],[]]` (order ভিন্ন হতে পারে; set হিসেবে সব 4টা subset)।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def subsets(nums):
out = []
def go(i, path):
if i == len(nums): # base case: সব item-এ সিদ্ধান্ত নেওয়া শেষ
out.append(path[:]) # snapshot! live path পরে বদলাবে
return
path.append(nums[i]) # CHOOSE: include nums[i]
go(i + 1, path) # EXPLORE
path.pop() # UN-CHOOSE
go(i + 1, path) # exclude nums[i]
go(0, [])
return out
# ---- order-independent তুলনার helper ----
def norm(list_of_lists):
return sorted([sorted(s) for s in list_of_lists])
# ---- tests ----
assert norm(subsets([1, 2, 3])) == norm(
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]])
assert len(subsets([1, 2, 3])) == 8 # 2^3
assert norm(subsets([0])) == norm([[], [0]])
assert subsets([]) == [[]] # খালি -> শুধু খালি subset
assert len(subsets([1, 2, 3, 4])) == 16 # 2^4
assert [] in subsets([1, 2]) # খালি subset সবসময় থাকে
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if i == len(nums):` — base case: শেষ index পেরোলে একটা সম্পূর্ণ subset তৈরি।
- `out.append(path[:])` — `path[:]` copy; live `path` পরে বদলাবে, তাই snapshot জরুরি।
- `path.append(nums[i])` — CHOOSE: এই item include করলাম।
- `go(i + 1, path)` — EXPLORE: পরের item-এ এগোও।
- `path.pop()` — UN-CHOOSE: include-এর সিদ্ধান্ত undo, যাতে exclude branch পরিষ্কার থাকে।
- `go(i + 1, path)` — exclude branch: এই item ছাড়াই বাকিটা।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`subsets([1,2,3])`: tree-র 8টা leaf-এ 8টা subset record হয় (`[]` থেকে `[1,2,3]`)। order ভিন্ন আসতে পারে, তাই `norm` দিয়ে sorted-of-sorted করে তুলনা করি — তাই assert stable। length 8 (=2^3), 4-element-এ 16, খালি input-এ `[[]]`। সব মিলে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function subsets(nums) {
const out = [];
const go = (i, path) => {
if (i === nums.length) { // base case: সব item-এ সিদ্ধান্ত শেষ
out.push([...path]); // snapshot! live path পরে বদলাবে
return;
}
path.push(nums[i]); // CHOOSE: include nums[i]
go(i + 1, path); // EXPLORE
path.pop(); // UN-CHOOSE
go(i + 1, path); // exclude nums[i]
};
go(0, []);
return out;
}
// ---- order-independent তুলনার helper ----
const norm = (lol) => JSON.stringify(lol.map(s => [...s].sort((a, b) => a - b)).sort((a, b) => JSON.stringify(a).localeCompare(JSON.stringify(b))));
// ---- test cases ----
assert(norm(subsets([1, 2, 3])) === norm([[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]), "main");
assert(subsets([1, 2, 3]).length === 8, "2^3");
assert(norm(subsets([0])) === norm([[], [0]]), "single");
assert(JSON.stringify(subsets([])) === JSON.stringify([[]]), "খালি -> [[]]");
assert(subsets([1, 2, 3, 4]).length === 16, "2^4");
assert(subsets([1, 2]).some(s => s.length === 0), "খালি subset আছে");
console.log("সব JS test pass!");
```
> **JS টীকা:** সবচেয়ে গুরুত্বপূর্ণ — `out.push([...path])` দিয়ে **snapshot** নাও; সরাসরি `out.push(path)` দিলে সব entry একই live array-র reference হয়ে শেষে খালি হয়ে যেত। `[...path]` (spread) বা `path.slice()` দুটোই copy বানায়। `path.pop()` ভুললে exclude branch-এ আগের choice leak করবে। sort-এ `(a, b) => a - b` দিতেই হবে, কারণ JS default sort সংখ্যাকেও string ধরে sort করে।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function subsets(nums: number[]): number[][] {
const out: number[][] = [];
const go = (i: number, path: number[]): void => {
if (i === nums.length) {
out.push([...path]); // snapshot
return;
}
path.push(nums[i]); // CHOOSE
go(i + 1, path); // EXPLORE
path.pop(); // UN-CHOOSE
go(i + 1, path); // exclude
};
go(0, []);
return out;
}
function expect