062 — Subset Generation using Bits¶

এখানে এসে bit আর set মিলে যায় — একটা সুন্দর মুহূর্ত। n টা element-এর প্রতিটার জন্য দুটো option: নেবো / নেবো না। সেই হ্যাঁ-না গুলো লিখলে একটা n-bit সংখ্যা! তাই 0 থেকে 2^n - 1 পর্যন্ত প্রতিটা সংখ্যা = একটা আলাদা subset-এর ছবি। recursion ছাড়াই, একটা loop দিয়ে সব subset। interview-তে "Subsets" নামে classic। Medium। চলো।

Source¶

Original source: LeetCode — Subsets
Platform: LeetCode — https://leetcode.com/problems/subsets/
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 পড়া)

1. Problem in simple words¶

একটা list দেওয়া আছে (ধরো সব element আলাদা)। তোমাকে এর সব subset (power set) বের করতে হবে — খালি set থেকে শুরু করে পুরো set পর্যন্ত।

যেমন [1, 2, 3]-এর subset গুলো:

{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

মোট 2^3 = 8 টা। n টা element হলে মোট 2^n টা subset।

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, একদম এক-এক মিল।

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 হয়ে ওঠে।

4. Real-life analogy¶

ভাবো তোমার সামনে n টা টপিং আছে — ধরো পিৎজার জন্য (পনির, মাশরুম, পেপারনি)। প্রতিটার জন্য একটাই সিদ্ধান্ত: দেবো নাকি দেবো না।

তুমি একটা checklist বানালে — প্রতিটা টপিং-এর পাশে টিক (নেবো) বা ফাঁকা (নেবো না)। প্রতিটা ভিন্ন checklist = একটা ভিন্ন পিৎজা (subset)। 3টা টপিং মানে 2^3 = 8 রকম পিৎজা — কোনো টপিং ছাড়া প্লেইন থেকে সব টপিং দেওয়া পর্যন্ত। সেই টিক-চিহ্নের সারিটাই binary mask।

5. Visual explanation¶

arr = [a, b, c] — প্রতিটা mask একটা subset (bit 0 = a, bit 1 = b, bit 2 = c):

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):

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} ✓

6. Example input and output¶

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) হওয়া দরকার।

7. Brute force thinking¶

bitmask না জানলে, recursion-ই সবচেয়ে স্বাভাবিক — প্রতিটা element-এ "নেবো / নেবো না" দুই ডালে ভাগ:

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" নয়, কিন্তু:

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 বানাও:

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) পুরো ভিত্তি।

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 বেরোয়।

12. Python solution¶

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¶

for mask in range(1 << n):

1 << n মানে 2^n। তাই mask 0 থেকে 2^n - 1 পর্যন্ত প্রতিটা মান নেয় — প্রতিটা একটা subset।

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 তৈরি।

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!।

14. Output walkthrough¶

চালালে যা ছাপবে (subset-এর ক্রম mask 0→7 অনুযায়ী):

[[], [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!।

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¶

range(1 << n) ভুলে range(n) লেখা — 3 element মানে 8টা subset, 3টা না! loop চলবে 2^n বার। (README #6।)
1 << n ভুলে n << 1 লেখা — 1 << 3 = 8 (সঠিক), 3 << 1 = 6 (ভুল)।
খালি subset ভুলে যাওয়া — mask = 0 দেয় {}, যেটা একটা বৈধ subset। loop 0 থেকে শুরু করতেই হবে।
bit আর index গুলিয়ে ফেলা — (mask >> i) & 1 দিয়ে i-তম bit, আর সেটা জ্বলা হলে arr[i]।
n বড় হলে memory ভাবা — 2^n exponential; n = 30 হলেই 10^9 subset, memory উড়ে যাবে।

18. Harder problems that inherit this idea¶

063 — Bitmask DP Intro (এই repo) — mask-কে DP-র state বানানো।
LeetCode — Subsets II (https://leetcode.com/problems/subsets-ii/) — duplicate element থাকলে subset।
LeetCode — Subsets (https://leetcode.com/problems/subsets/) — এই problem-এরই মূল রূপ।
USACO Guide — DP Bitmasks (https://usaco.guide/gold/dp-bitmasks) — subset enumeration থেকে bitmask DP-তে উত্তরণ।

19. Pattern learned¶

Bitmask subset enumeration — 0 থেকে 2^n - 1 loop, প্রতিটা mask-এর জ্বলা bit (mask >> i) & 1 দিয়ে subset বানানো। বড় শিক্ষা: প্রতিটা subset একটা হ্যাঁ/না checklist = একটা binary সংখ্যা; তাই subset enumerate করা মানে শুধু গোনা, recursion লাগে না। এই mask = subset mapping-ই bitmask DP-র দরজা।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "সব subset = for mask in range(1 << n), প্রতিটা mask-এর জ্বলা bit দিয়ে element নাও। subset = checklist = সংখ্যা; n ≤ 20 দেখলেই bitmask মনে করব। এটাই bitmask DP-র ভিত্তি।"

পরের ধাপ → 063 — Bitmask DP Intro (এবার mask-কে DP-র state বানাব — পুরো visited set একটা int-এ)। সম্পর্কিত → 054 — Check ith Bit।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নেই — বরং "common interview pattern" / "Google-style pattern"।