Problem link ও উৎস
- **Original source:** LeetCode — Subsets
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 4: Bit Manipulation → subset enumeration
- **Difficulty:** Medium
- **Pattern:** bitmask enumeration (0 থেকে 2^n - 1, প্রতিটা mask = একটা subset)
- **Basic idea inherited from:** 047 (subset counting, 2^n) আর 054 — Check ith Bit (bit পড়া)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা list দেওয়া আছে (ধরো সব element আলাদা)। তোমাকে এর **সব subset** (power set) বের করতে হবে — খালি set থেকে শুরু করে পুরো set পর্যন্ত।
যেমন `[1, 2, 3]`-এর subset গুলো:
```text
{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}
```
মোট `2^3 = 8` টা। n টা element হলে মোট `2^n` টা subset।
### Input ও output {#6-example-input-and-output}
```text
input -> output (2^n টা subset)
---------------------------------------
[1, 2, 3] -> [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
[1] -> [[], [1]]
[] -> [[]] (খালি list-এর একটা subset: খালি set)
[7, 8] -> [[], [7], [8], [7,8]]
```
edge case: খালি list `[]` → ঠিক একটা subset, খালি set `[[]]` (কারণ `2^0 = 1`)। আর n বড় হলে output exponentially বাড়ে — তাই n ছোট (≤ 20) হওয়া দরকার।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার সামনে `n` টা টপিং আছে — ধরো পিৎজার জন্য (পনির, মাশরুম, পেপারনি)। প্রতিটার জন্য একটাই সিদ্ধান্ত: দেবো নাকি দেবো না।
তুমি একটা checklist বানালে — প্রতিটা টপিং-এর পাশে টিক (নেবো) বা ফাঁকা (নেবো না)। প্রতিটা ভিন্ন checklist = একটা ভিন্ন পিৎজা (subset)। 3টা টপিং মানে `2^3 = 8` রকম পিৎজা — কোনো টপিং ছাড়া প্লেইন থেকে সব টপিং দেওয়া পর্যন্ত। সেই টিক-চিহ্নের সারিটাই binary mask।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
দুটো জিনিস থেকে এসেছে:
- **047 (subset counting)** — সেখানে শিখেছ n টা জিনিসের subset সংখ্যা ঠিক `2^n` (প্রতিটায় নেওয়া/না-নেওয়া)। এখানে সেই গোনাটাকে সত্যি **বানিয়ে** দেখাচ্ছি।
- **054 (Check ith Bit)** — প্রতিটা mask-এর কোন bit জ্বলা সেটা পড়তে লাগে `(mask >> i) & 1`।
মানে 062 = "2^n subset আছে" (counting) + "bit দিয়ে কোনটা আছে পড়া" (check)। আর এই bitmask enumeration হলো **063 (Bitmask DP Intro)**-এর সরাসরি ভিত্তি — সেখানে mask DP-র state হয়ে ওঠে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea: **প্রতিটা subset = একটা checklist।** n টা element-এর প্রতিটার জন্য একটা হ্যাঁ/না — "এই element কি subset-এ আছে?" এই n টা হ্যাঁ/না-কে 0/1 দিয়ে লিখলে একটা **n-bit সংখ্যা (mask)** তৈরি হয়।
তাই 0 থেকে `2^n - 1` পর্যন্ত প্রতিটা সংখ্যাই একটা আলাদা subset-কে represent করে:
- mask-এর `i`-তম bit জ্বলা → `arr[i]` subset-এ আছে
- নেভানো → নেই
`2^n` টা mask = `2^n` টা subset, একদম এক-এক মিল।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
bitmask না জানলে, recursion-ই সবচেয়ে স্বাভাবিক — প্রতিটা element-এ "নেবো / নেবো না" দুই ডালে ভাগ:
```python
def subsets_recursive(arr):
result = []
def helper(i, current):
if i == len(arr):
result.append(current[:]) # একটা subset শেষ
return
helper(i + 1, current) # arr[i] নিলাম না
current.append(arr[i])
helper(i + 1, current) # arr[i] নিলাম
current.pop()
helper(0, [])
return result
```
কাজ করে — দুই ডালে ভাগ করে প্রতিটা পথ একটা subset। কিন্তু recursion stack লাগে, আর mask-এর সাথে subset-এর সরাসরি সুন্দর mapping-টা হারিয়ে যায়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
আসলে দুটোরই complexity একই — O(2^n × n) (subset সংখ্যা × প্রতিটা বানানোর খরচ)। recursion "slow" নয়, কিন্তু:
```text
recursion : call stack লাগে (O(n) depth), mask mapping লুকানো
bitmask : কোনো stack নেই, প্রতিটা subset-কে সরাসরি একটা সংখ্যা দিয়ে চেনা যায়
```
bitmask-এর আসল সুবিধা — প্রতিটা subset-এর একটা নম্বর (mask) থাকে, যেটা পরে DP-তে (063) state হিসেবে index করা যায়। recursion-এ সেই হাতল নেই।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
0 থেকে `2^n - 1` loop চালাও, প্রতিটা mask-এর জ্বলা bit গুলো তুলে subset বানাও:
```python
def subsets(arr):
n = len(arr)
result = []
for mask in range(1 << n): # 0 .. 2^n - 1
subset = [arr[i] for i in range(n) if (mask >> i) & 1]
result.append(subset)
return result
```
একটা outer loop (`2^n` বার) আর একটা inner loop (n বার bit পড়া)। কোনো recursion নেই, mask সরাসরি subset-এর নাম।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **প্রতিটা subset আসলে একটা হ্যাঁ/না checklist, আর সেই checklist-ই একটা binary সংখ্যা; তাই 0 থেকে 2^n-1 গুনে গেলে প্রতিটা সংখ্যা একটা subset হয়ে যায় — আলাদা করে subset "বানাতে" হয় না, শুধু সংখ্যা গুনলেই হয়।**
subset-কে অনেকে recursion বা combination দিয়ে ভাবে। কিন্তু bit-চোখে: "নেবো/নেবো না" তো একটা bit! n টা সিদ্ধান্ত = n bit = একটা সংখ্যা। তাই subset enumerate করা মানে শুধু 0 থেকে `2^n - 1` পর্যন্ত গোনা, আর প্রতিটা সংখ্যার জ্বলা bit গুলো পড়া (054)। এই "checklist = সংখ্যা" mapping-টাই পরে bitmask DP-র (063) পুরো ভিত্তি।
### ছবিতে বোঝা {#5-visual-explanation}
`arr = [a, b, c]` — প্রতিটা mask একটা subset (bit 0 = a, bit 1 = b, bit 2 = c):
```text
mask binary কোন bit জ্বলা subset
0 0 0 0 কেউ না {}
1 0 0 1 bit 0 {a}
2 0 1 0 bit 1 {b}
3 0 1 1 bit 0,1 {a, b}
4 1 0 0 bit 2 {c}
5 1 0 1 bit 0,2 {a, c}
6 1 1 0 bit 1,2 {b, c}
7 1 1 1 সবাই {a, b, c}
```
একটা mask কীভাবে subset-এ রূপ নেয় (`mask = 5 = 101`):
```text
i=0: (5 >> 0) & 1 = 1 -> arr[0]=a নাও
i=1: (5 >> 1) & 1 = 0 -> arr[1]=b বাদ
i=2: (5 >> 2) & 1 = 1 -> arr[2]=c নাও
subset = {a, c} ✓
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`arr = [a, b, c]`, কয়েকটা mask:
| mask | binary | bit 0 (a) | bit 1 (b) | bit 2 (c) | subset |
| --- | --- | --- | --- | --- | --- |
| 0 | 000 | 0 | 0 | 0 | {} |
| 1 | 001 | 1 | 0 | 0 | {a} |
| 3 | 011 | 1 | 1 | 0 | {a, b} |
| 5 | 101 | 1 | 0 | 1 | {a, c} |
| 7 | 111 | 1 | 1 | 1 | {a, b, c} |
`mask = 5`-এর বিস্তারিত: `(5>>0)&1=1` (a নাও), `(5>>1)&1=0` (b বাদ), `(5>>2)&1=1` (c নাও) → `{a, c}` ✓। loop 0 থেকে 7 চললে সব 8টা subset বেরোয়।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def subsets(arr):
"""arr-এর সব subset (power set) bitmask দিয়ে generate করে।"""
n = len(arr)
result = []
for mask in range(1 << n): # 0 থেকে 2^n - 1
subset = [arr[i] for i in range(n) if (mask >> i) & 1]
result.append(subset)
return result
def subsets_recursive(arr):
"""একই subset গুলো recursion দিয়ে (যাচাইয়ের জন্য)।"""
result = []
def helper(i, current):
if i == len(arr):
result.append(current[:])
return
helper(i + 1, current)
current.append(arr[i])
helper(i + 1, current)
current.pop()
helper(0, [])
return result
# --- ছোট test গুলো (সব pass করা উচিত) ---
# subset সংখ্যা সবসময় 2^n
assert len(subsets([1, 2, 3])) == 8
assert len(subsets([1])) == 2
assert len(subsets([])) == 1 # খালি list -> [[]]
assert subsets([]) == [[]]
# প্রতিটা subset একবার করে আছে, আর mask mapping ঠিক
s = subsets([1, 2, 3])
as_sets = sorted(sorted(sub) for sub in s)
expected = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
assert as_sets == expected
# bitmask আর recursion একই subset-সংগ্রহ দেয় (ক্রম বাদে)
def normalize(lst):
return sorted(tuple(sorted(sub)) for sub in lst)
for arr in [[], [9], [1, 2], [3, 5, 7], [1, 2, 3, 4]]:
assert normalize(subsets(arr)) == normalize(subsets_recursive(arr))
assert len(subsets(arr)) == 2 ** len(arr)
print(subsets([1, 2, 3]))
print("subset count:", len(subsets([1, 2, 3]))) # 8
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
for mask in range(1 << n):
```
`1 << n` মানে `2^n`। তাই mask 0 থেকে `2^n - 1` পর্যন্ত প্রতিটা মান নেয় — প্রতিটা একটা subset।
```text
subset = [arr[i] for i in range(n) if (mask >> i) & 1]
```
এটাই হৃদয়। প্রতিটা index `i`-র জন্য চেক করি `(mask >> i) & 1` (054-এর check) — `i`-তম bit জ্বলা হলে `arr[i]` subset-এ নিই। এক লাইনের list comprehension-এ পুরো subset তৈরি।
```text
helper(i + 1, current) # নিলাম না
current.append(arr[i]); helper(i + 1, current); current.pop() # নিলাম
```
recursion version: প্রতিটা element-এ দুই ডাল — না-নিয়ে আর নিয়ে। যাচাইয়ের জন্য।
`assert` লাইনগুলো subset সংখ্যা (`2^n`), প্রতিটা subset-এর উপস্থিতি, আর দুই method-এর মিল যাচাই করছে। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে (subset-এর ক্রম mask 0→7 অনুযায়ী):
```text
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
subset count: 8
সব test pass!
```
প্রথম লাইন `subsets([1,2,3])` — 8টা subset, mask 0 (`{}`) থেকে mask 7 (`{1,2,3}`) ক্রমে। দ্বিতীয় লাইন count = 8 (`2^3`)। সব `assert` চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(2^n × n)** — `2^n` টা mask, প্রতিটার জন্য n টা bit পড়ে subset বানাই। তাই n ছোট (সাধারণত ≤ 20) হলেই এই পথ চলে; বড় n-এ output নিজেই বিশাল।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(2^n × n)** — output-এ সব subset রাখতে হয় (`2^n` টা subset, গড়ে n/2 element)। শুধু generate করে process করলে (store না করলে) auxiliary space O(n)।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`range(1 << n)` ভুলে `range(n)` লেখা** — 3 element মানে 8টা subset, 3টা না! loop চলবে `2^n` বার। (README #6।)
2. **`1 << n` ভুলে `n << 1` লেখা** — `1 << 3 = 8` (সঠিক), `3 << 1 = 6` (ভুল)।
3. **খালি subset ভুলে যাওয়া** — `mask = 0` দেয় `{}`, যেটা একটা বৈধ subset। loop 0 থেকে শুরু করতেই হবে।
4. **bit আর index গুলিয়ে ফেলা** — `(mask >> i) & 1` দিয়ে `i`-তম bit, আর সেটা জ্বলা হলে `arr[i]`।
5. **n বড় হলে memory ভাবা** — `2^n` exponential; n = 30 হলেই 10^9 subset, memory উড়ে যাবে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **063 — Bitmask DP Intro** (এই repo) — mask-কে DP-র state বানানো।
- **LeetCode — Subsets II** (