Problem link ও উৎস
- **Original source:** Concept link — LeetCode Subsets
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 3: Counting & Combinatorics
- **Difficulty:** Easy
- **Pattern:** 2^n choices (subset counting)
- **Basic idea inherited from:** 041 — Combination Basic (সব r-এর C(n,r)-এর যোগ = 2^n)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n` টা আলাদা জিনিসের একটা set আছে। তার কতগুলো **subset** (উপসেট) আছে?
subset মানে — মূল set থেকে যেকোনো কিছু (শূন্যটা থেকে সবকটা পর্যন্ত) বেছে বানানো দল। খালি set `{}`-ও একটা subset, পুরো set-ও একটা subset।
যেমন `{a, b}`-এর subset: `{}`, `{a}`, `{b}`, `{a, b}` — মোট 4টা।
উত্তর সবসময় `2ⁿ`। কখনো প্রশ্ন আসে "non-empty subset কয়টা?" — তখন খালি set বাদ দিয়ে `2ⁿ − 1`।
### Input ও output {#6-example-input-and-output}
```text
n -> subset সংখ্যা (2^n) -> non-empty (2^n − 1)
---------------------------------------------------
0 -> 1 -> 0 (শুধু খালি set)
1 -> 2 -> 1 ({}, {a})
2 -> 4 -> 3
3 -> 8 -> 7
4 -> 16 -> 15
10 -> 1024 -> 1023
```
Edge case: **n = 0 → 1 subset** (শুধু খালি set `{}` — অনেকে ভুল করে 0 ভাবে)। আর non-empty version-এ n=0 হলে 0 (খালি set বাদ দিলে কিছু থাকে না)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা পিৎজা অর্ডার করছ, আর `n` টা topping পাওয়া যায় — পনির, মাশরুম, ক্যাপসিকাম, ... । তুমি কতগুলো আলাদা পিৎজা বানাতে পারো?
প্রতিটা topping-এর জন্য তোমার একটাই সিদ্ধান্ত: "এটা দেব? হ্যাঁ/না।" — 2 রকম। সিদ্ধান্তগুলো একে অন্যের উপর নির্ভর করে না।
- 3 topping হলে: 2 × 2 × 2 = 8 রকম পিৎজা (একদম প্লেইন থেকে সব-দেওয়া পর্যন্ত)।
"প্লেইন পিৎজা" (কোনো topping নেই) = খালি subset; "সব topping" = পুরো set। তাই মোট পিৎজা = subset সংখ্যা = `2ⁿ`। non-empty চাইলে (অন্তত একটা topping) → `2ⁿ − 1`।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা **041 (Combination Basic)**-এর সাথে গভীরভাবে জড়িত। দুই দিক থেকে:
- **C-দের যোগ:** প্রতিটা আকারের subset-সংখ্যা `C(n, r)`; সব আকার মিলিয়ে `ΣC(n,r) = 2ⁿ`। মানে subset গোনা = সব combination একসাথে গোনা।
- **নতুন কৌশল:** কিন্তু একে একে `C(n,r)` যোগ না করেও সরাসরি 2ⁿ পাওয়া যায় — "প্রতিটার হ্যাঁ/না" multiplication principle দিয়ে। এই "প্রতিটা element-এর স্বাধীন binary choice" idea-ই 047-এর নতুন অবদান।
আর 042-এর Pascal triangle-এ দেখেছিলে প্রতি সারির যোগফল 1,2,4,8,16 — সেটাই এই 2ⁿ, এখানে তার মানে খুলল।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **প্রতিটা জিনিসের জন্য একটাই স্বাধীন হ্যাঁ/না সিদ্ধান্ত।**
subset বানাতে গিয়ে প্রতিটা জিনিসকে জিজ্ঞেস করো: "তুমি কি এই subset-এ আছ?" — উত্তর হয় হ্যাঁ, নয় না (2 choice)। n টা জিনিসের জন্য n টা স্বাধীন হ্যাঁ/না। multiplication principle:
```text
subset সংখ্যা = 2 × 2 × ... × 2 (n বার) = 2ⁿ
```
আরেকটা চেহারা: subset-এর আকার 0, 1, 2, ..., n যেকোনো হতে পারে, তাই মোট = `C(n,0) + C(n,1) + ... + C(n,n) = 2ⁿ` (binomial theorem-এর সুন্দর ফল)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরাসরি — **সত্যিই সব subset বানিয়ে গুনে ফেলা।** Python-এ 0 থেকে 2ⁿ−1 প্রতিটা সংখ্যার bit দেখে subset তৈরি করা যায়:
```python
def list_subsets(items):
n = len(items)
result = []
for mask in range(1 << n): # 0 .. 2^n − 1
subset = [items[i] for i in range(n) if mask & (1 << i)]
result.append(subset)
return result
def count_subsets_brute(items):
return len(list_subsets(items))
```
প্রতিটা `mask` (binary সংখ্যা) একটা subset বোঝায়; সব বানিয়ে গুনি। ছোট n-এ একদম ঠিক — আর `2ⁿ` formula verify করার নিখুঁত উপায় (subset গুলো চোখেও দেখা যায়)।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা হলো subset-এর **সংখ্যাই** `2ⁿ` — exponential! সব বানিয়ে গুনলে ততগুলো ধাপ লাগে:
```text
n = 20 হলে: 2^20 ≈ 10 লক্ষ subset -> চলে, কিন্তু ভারী
n = 40 হলে: 2^40 ≈ 10^12 subset -> অসম্ভব, memory-ও শেষ
n = 64 হলে: 2^64 -> মহাজাগতিক
শুধু সংখ্যাটা চাইলে: 2 ** n -> এক ধাপে, O(1)!
```
subset **তালিকা** চাইলে exponential কাজ অনিবার্য (output-ই বড়)। কিন্তু শুধু **সংখ্যা** চাইলে একে একে বানানো বিরাট অপচয় — formula এক নিমেষে দেয়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: subset গুনতে হলে সত্যিই বানানোর দরকার নেই — **প্রতিটা element-এর হ্যাঁ/না** থেকে সরাসরি:
```python
def count_subsets(n):
return 2 ** n
def count_non_empty_subsets(n):
return 2 ** n - 1 # খালি set বাদ
```
`2 ** n` Python-এ এক ধাপে বিশাল সংখ্যাও সামলায়। আর কেন এটা ঠিক — সেটা multiplication principle থেকে: n টা স্বাধীন binary choice।
(যদি subset-গুলো সত্যিই **দরকার** হয় — যেমন LeetCode Subsets — তখন bitmask বা backtracking দিয়ে generate, কিন্তু শুধু গোনায় formula-ই যথেষ্ট।)
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **প্রতিটা জিনিসকে আলাদা করে দেখো — তার কাছে শুধু একটাই প্রশ্ন: "ভেতরে? হ্যাঁ/না।" n টা স্বাধীন হ্যাঁ/না = 2ⁿ।**
এই "প্রতিটা element-এর independent binary choice" চিন্তাটা অসম্ভব শক্তিশালী। আর তার যমজ tweak: **প্রতিটা subset = একটা n-bit binary সংখ্যা** (0 = নেই, 1 = আছে), তাই subset গোনা = 0 থেকে 2ⁿ−1 পর্যন্ত সংখ্যা গোনা। এই দুই চিন্তা একসাথে Level 4-এর bitmask-এর পুরো ভিত গড়ে দেয়।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দেখো "প্রতিটার হ্যাঁ/না" গাছ ({a, b, c}):
```text
a?
হ্যাঁ / \ না
b? b?
হ্যা/ \না হ্যা/ \না
c? c? c? c?
হ্যা\না ... (প্রতিটা পাতা = একটা subset)
3 টা হ্যাঁ/না -> 2 × 2 × 2 = 8 পাতা = 8 subset
```
এবার দেখো প্রতিটা subset = একটা binary pattern (Level 4-এর সেতু):
```text
{a, b, c}: প্রতিটা bit = "আছে কিনা" (a=বাঁ, c=ডান)
000 -> {} 100 -> {a}
001 -> {c} 101 -> {a, c}
010 -> {b} 110 -> {a, b}
011 -> {b, c} 111 -> {a, b, c}
0 থেকে 2³−1 = 7 পর্যন্ত প্রতিটা সংখ্যা = একটা subset
মোট 8 = 2³ ✓
```
লক্ষ করো — 0 থেকে 2ⁿ−1 পর্যন্ত প্রতিটা সংখ্যা ঠিক একটা subset; এটাই bit manipulation-এর ভিত।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো `items = ['a', 'b']` (n=2) — সব subset bitmask দিয়ে বানাই, formula `2² = 4`:
| mask (binary) | কোন bit on | subset |
| --- | --- | --- |
| 0 (00) | কিছু না | `{}` |
| 1 (01) | bit 0 (a) | `{a}` |
| 2 (10) | bit 1 (b) | `{b}` |
| 3 (11) | bit 0, 1 | `{a, b}` |
মোট 4টা subset — formula `2² = 4`-এর সাথে মিলল ✓। non-empty হলে খালিটা বাদ → 3।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def count_subsets(n):
"""n জিনিসের set-এর কতগুলো subset = 2^n।"""
return 2 ** n
def count_non_empty_subsets(n):
"""খালি set বাদ দিয়ে subset সংখ্যা = 2^n − 1।"""
return 2 ** n - 1
def list_subsets(items):
"""সব subset bitmask দিয়ে বানিয়ে list (verify ও বোঝার জন্য)।"""
n = len(items)
result = []
for mask in range(1 << n): # 0 .. 2^n − 1
subset = [items[i] for i in range(n) if mask & (1 << i)]
result.append(subset)
return result
# --- ছোট test গুলো (সব pass করা উচিত) ---
# formula সঠিক কিনা
assert count_subsets(0) == 1 # শুধু খালি set
assert count_subsets(1) == 2
assert count_subsets(2) == 4
assert count_subsets(3) == 8
assert count_subsets(10) == 1024
assert count_non_empty_subsets(0) == 0
assert count_non_empty_subsets(3) == 7
# formula == সত্যিই বানানো subset-এর সংখ্যা (brute, n=0..12)
for n in range(0, 13):
items = list(range(n))
assert count_subsets(n) == len(list_subsets(items))
# ΣC(n,r) == 2^n (combination-যোগের সাথে মিল)
import math
for n in range(0, 13):
assert sum(math.comb(n, r) for r in range(n + 1)) == count_subsets(n)
# list_subsets-এ কোনো subset দুবার নেই, আর খালি+পূর্ণ দুটোই আছে
subs = list_subsets(['a', 'b', 'c'])
as_sets = [frozenset(s) for s in subs]
assert len(as_sets) == len(set(as_sets)) == 8 # সব আলাদা, মোট 8
assert frozenset() in as_sets # খালি set আছে
assert frozenset(['a', 'b', 'c']) in as_sets # পূর্ণ set আছে
print(count_subsets(3)) # 8
print(count_non_empty_subsets(3)) # 7
print(list_subsets(['a', 'b'])) # [[], ['a'], ['b'], ['a', 'b']]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def count_subsets(n):
return 2 ** n
```
মূল formula — প্রতিটা element-এর হ্যাঁ/না, n টা স্বাধীন choice → 2ⁿ। n=0-এ `2**0 = 1` (খালি set) — আপনাআপনি ঠিক।
```text
def count_non_empty_subsets(n):
return 2 ** n - 1
```
খালি set একটাই, সেটা বাদ দিলে `2ⁿ − 1`।
```text
for mask in range(1 << n):
subset = [items[i] for i in range(n) if mask & (1 << i)]
```
verify-র জন্য সত্যিই বানানো — প্রতিটা `mask` (0..2ⁿ−1) একটা subset; `mask & (1 << i)` চেক করে i-তম element ভেতরে কিনা (bit on কিনা)। `1 << n` মানে 2ⁿ।
বাকি `assert` লাইনগুলো formula-কে (১) সত্যিই বানানো সংখ্যার সাথে, (২) `ΣC(n,r)`-এর সাথে, (৩) subset-গুলো আলাদা ও পূর্ণ — সব দিক যাচাই করছে। সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
8
7
[[], ['a'], ['b'], ['a', 'b']]
সব test pass!
```
প্রথম: `count_subsets(3)` = 8 (2³)। দ্বিতীয়: non-empty = 7। তৃতীয়: `list_subsets(['a','b'])`-এর 4টা subset (খালি থেকে পূর্ণ)। আগের সব `assert` (বানানো সংখ্যা, ΣC(n,r), uniqueness — তিন দিক) চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
`count_subsets(n)` **O(1)** — শুধু একটা `2 ** n` (গণিত-অপারেশন; বিশাল n-এ সংখ্যার আকারের সাথে সামান্য খরচ, তবু interview-মাপে O(1))। subset **তালিকা** (`list_subsets`) চাইলে **O(n · 2ⁿ)** — প্রতিটা subset বানাতে O(n)।
### অতিরিক্ত জায়গা {#16-space-complexity}
`count_subsets` **O(1)** — শুধু একটা সংখ্যা। `list_subsets` **O(n · 2ⁿ)** — সব subset জমিয়ে রাখতে।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **n=0-এ 0 ভাবা** — খালি set-ও একটা subset, তাই `2⁰ = 1`, 0 নয়।
2. **খালি set ভুলে যাওয়া** — subset গোনায় `{}` অবশ্যই ধরা হয়; non-empty চাইলেই কেবল বাদ।
3. **শুধু সংখ্যা চাইলেও সব subset বানানো** — exponential কাজ; গোনায় `2 ** n` যথেষ্ট।
4. **2ⁿ আর n² গুলিয়ে ফেলা** — subset 2ⁿ (exponential), n² নয়; বিশাল পার্থক্য।
5. **non-empty/empty নিয়ে দ্বিধা** — প্রশ্নে "non-empty" থাকলে `−1`, নাহলে নয় — মন দিয়ে পড়ো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Subsets** (