047 — Count Subsets¶
এবার দল নয়, সব রকম দল একসাথে — একটা set-এর কতগুলো subset হয়? উত্তরটা মন্ত্রমুগ্ধকর সরল:
2ⁿ। আর এর পেছনের গল্পটা পুরো combinatorics-এর সবচেয়ে মিষ্টি idea-গুলোর একটা: প্রতিটা জিনিসকে একটাই প্রশ্ন — "তুমি কি ভেতরে? হ্যাঁ/না।" এই 2ⁿ পরের Level 4 (bit manipulation)-এ প্রতিটা subset একটা binary সংখ্যা হয়ে ফিরবে — তাই এটা একটা সেতু।
Source¶
- Original source: Concept link — LeetCode Subsets
- Platform: LeetCode — https://leetcode.com/problems/subsets/
- 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)
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।
2. What is the math idea?¶
মূল idea — প্রতিটা জিনিসের জন্য একটাই স্বাধীন হ্যাঁ/না সিদ্ধান্ত।
subset বানাতে গিয়ে প্রতিটা জিনিসকে জিজ্ঞেস করো: "তুমি কি এই subset-এ আছ?" — উত্তর হয় হ্যাঁ, নয় না (2 choice)। n টা জিনিসের জন্য n টা স্বাধীন হ্যাঁ/না। multiplication principle:
আরেকটা চেহারা: subset-এর আকার 0, 1, 2, ..., n যেকোনো হতে পারে, তাই মোট = C(n,0) + C(n,1) + ... + C(n,n) = 2ⁿ (binomial theorem-এর সুন্দর ফল)।
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ⁿ, এখানে তার মানে খুলল।
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।
5. Visual explanation¶
প্রথমে দেখো "প্রতিটার হ্যাঁ/না" গাছ ({a, b, c}):
a?
হ্যাঁ / \ না
b? b?
হ্যা/ \না হ্যা/ \না
c? c? c? c?
হ্যা\না ... (প্রতিটা পাতা = একটা subset)
3 টা হ্যাঁ/না -> 2 × 2 × 2 = 8 পাতা = 8 subset
এবার দেখো প্রতিটা subset = একটা binary pattern (Level 4-এর সেতু):
{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-এর ভিত।
6. Example input and output¶
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 বাদ দিলে কিছু থাকে না)।
7. Brute force thinking¶
সবচেয়ে সরাসরি — সত্যিই সব subset বানিয়ে গুনে ফেলা। Python-এ 0 থেকে 2ⁿ−1 প্রতিটা সংখ্যার bit দেখে subset তৈরি করা যায়:
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! সব বানিয়ে গুনলে ততগুলো ধাপ লাগে:
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-এর হ্যাঁ/না থেকে সরাসরি:
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-এর পুরো ভিত গড়ে দেয়।
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।
12. Python solution¶
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¶
মূল formula — প্রতিটা element-এর হ্যাঁ/না, n টা স্বাধীন choice → 2ⁿ। n=0-এ 2**0 = 1 (খালি set) — আপনাআপনি ঠিক।
খালি set একটাই, সেটা বাদ দিলে 2ⁿ − 1।
verify-র জন্য সত্যিই বানানো — প্রতিটা mask (0..2ⁿ−1) একটা subset; mask & (1 << i) চেক করে i-তম element ভেতরে কিনা (bit on কিনা)। 1 << n মানে 2ⁿ।
বাকি assert লাইনগুলো formula-কে (১) সত্যিই বানানো সংখ্যার সাথে, (২) ΣC(n,r)-এর সাথে, (৩) subset-গুলো আলাদা ও পূর্ণ — সব দিক যাচাই করছে। সব মিললে শেষে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম: count_subsets(3) = 8 (2³)। দ্বিতীয়: non-empty = 7। তৃতীয়: list_subsets(['a','b'])-এর 4টা subset (খালি থেকে পূর্ণ)। আগের সব assert (বানানো সংখ্যা, ΣC(n,r), uniqueness — তিন দিক) চুপচাপ pass করেছে। শেষে সব test pass!।
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¶
- n=0-এ 0 ভাবা — খালি set-ও একটা subset, তাই
2⁰ = 1, 0 নয়। - খালি set ভুলে যাওয়া — subset গোনায়
{}অবশ্যই ধরা হয়; non-empty চাইলেই কেবল বাদ। - শুধু সংখ্যা চাইলেও সব subset বানানো — exponential কাজ; গোনায়
2 ** nযথেষ্ট। - 2ⁿ আর n² গুলিয়ে ফেলা — subset 2ⁿ (exponential), n² নয়; বিশাল পার্থক্য।
- non-empty/empty নিয়ে দ্বিধা — প্রশ্নে "non-empty" থাকলে
−1, নাহলে নয় — মন দিয়ে পড়ো।
18. Harder problems that inherit this idea¶
- LeetCode — Subsets (https://leetcode.com/problems/subsets/) — সব subset সত্যিই generate করা (bitmask/backtracking)।
- LeetCode — Subsets II (https://leetcode.com/problems/subsets-ii/) — duplicate থাকলে distinct subset।
- Level 4 — Bit Manipulation (এই module-এর পরের level) — প্রতিটা subset একটা bitmask, এখানকার 2ⁿ-ই সেখানে কাঠামো।
19. Pattern learned¶
Subset counting via 2ⁿ (independent yes/no per element) — প্রতিটা জিনিসের হ্যাঁ/না, n টা স্বাধীন choice → 2ⁿ; non-empty হলে 2ⁿ−1। সাথে: প্রতিটা subset = একটা n-bit সংখ্যা। মূল signal: "কতগুলো subset / কত রকম বাছাই (প্রতিটা নেওয়া-না-নেওয়া)" দেখলেই 2ⁿ।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "subset সংখ্যা = 2ⁿ (প্রতিটার হ্যাঁ/না), non-empty 2ⁿ−1; খালি set গোনে, তাই 2⁰=1। প্রতিটা subset = একটা binary সংখ্যা — Level 4-এর সেতু।"
পরের ধাপ → 048 — Count Paths in Grid (grid-এ হাঁটা = R/D সাজানো — C(m+n, n))।
ফিরে দেখা: আগের ধাপ → 041 — Combination Basic · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নয় — বরং "common interview pattern" / "Google-style pattern"।