007 — Subsets¶

Source¶

Original source: Classic backtracking exercise (power set)
Platform: LeetCode — https://leetcode.com/problems/subsets/
Topic: recursion / backtracking (include-exclude branch)
Difficulty: Medium
Pattern: include/exclude branch — প্রতিটা item নাও বা বাদ দাও (2^n)
Basic idea inherited from: decrease-and-conquer, এবার branching সহ

1. Problem in simple words¶

একটা সংখ্যার list nums দেওয়া আছে (সব আলাদা)। তোমার কাজ: এর সব subset (power set) বের করা — মানে যত রকমভাবে কিছু element বেছে নেওয়া যায়, প্রতিটা সংগ্রহ। খালি subset [] আর পুরো list দুটোই গোনা। nটা element-এর জন্য মোট 2^nটা subset।

nums = [1, 2, 3]
subsets = [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]   (মোট 8 = 2^3)

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 জরুরি।

6. Real-life analogy¶

একটা পিৎজার toppings মেনু ভাবো: পনির, মাশরুম, লঙ্কা। প্রতিটা topping-এর জন্য তুমি হয় "হ্যাঁ দাও" নয় "না থাক" বলো। সব সম্ভাব্য পিৎজা = প্রতিটা topping-এ হ্যাঁ/না-এর সব সংমিশ্রণ — কিছুই না দেওয়া (plain) থেকে সব দেওয়া (deluxe) পর্যন্ত। প্রতিটা item-এ স্বাধীন দুটো choice-ই সব subset তৈরি করে।

7. Visual explanation¶

প্রতি index-এ দুটো branch — left = include, right = exclude। [1, 2]-এর decision tree:

                    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।

8. Example input and output¶

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]

9. Brute force thinking¶

প্রথম সরল চিন্তা: 0 থেকে 2^n - 1 পর্যন্ত প্রতিটা সংখ্যাকে একটা bitmask ধরে নাও; যে bit 1, সেই index-এর element subset-এ ঢোকাও।

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 সমস্যাটা একটা ছোট, দুই-শাখার সিদ্ধান্তে নেমে আসে।

14. Step-by-step dry run¶

subsets([1, 2]), go(i, path):

go(0,[]) → include 1: path=[1], go(1,[1])।
go(1,[1]) → include 2: path=[1,2], go(2,[1,2]): i==2 → record [1,2]; pop → [1]।
go(1,[1]) → exclude 2: go(2,[1]): record [1]; ফিরে pop 1 → []।
go(0,[]) → exclude 1: go(1,[]) → include 2: record [2], pop; exclude 2: record []।
out = [[1,2],[1],[2],[]] (order ভিন্ন হতে পারে; set হিসেবে সব 4টা subset)।

15. Python solution¶

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 ছাড়াই বাকিটা।

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

18. Time complexity¶

O(n · 2^n) — 2^n subset, প্রতিটার snapshot নিতে n পর্যন্ত copy।

19. Space complexity¶

Output বাদ দিলে O(n) — path-এর গভীরতা ও call stack n পর্যন্ত। Output ধরলে O(n · 2^n)।

20. Common mistakes¶

out.append(path) লেখা (snapshot ছাড়া) — সব entry একই live list-এর reference হয়ে শেষে খালি/ভুল হয়ে যায়; path[:] নাও।
include-এর পর path.pop() ভুলে যাওয়া — exclude branch-এ আগের choice leak করে।
base case-এ record না করে শুধু return — কোনো subset জমে না।
duplicate input থাকলে এই version duplicate subset দেবে — তখন Subsets II-র sort-and-skip লাগে।

21. Which basic problem this inherits from¶

ভিত্তি: decrease-and-conquer (এক item করে এগোনো) + branching। ../patterns.md-এর Pattern 3 (Subsets — include/exclude) আর ../concept.md-এর choose/explore/un-choose frame দেখো। এটা tracker-এর চারটা canonical interview shape-এর একটা — এখানে সবচেয়ে বেশি সময় দাও।

22. Similar harder problems¶

Subsets II (duplicate সহ) — https://leetcode.com/problems/subsets-ii/ (এই tracker-এর #10)
Combinations (fixed size k) — https://leetcode.com/problems/combinations/ (#11)
Permutations (ordering matters) — https://leetcode.com/problems/permutations/ (#9)

23. Pattern learned¶

Include/exclude branching: প্রতিটা item-এ ঠিক দুটো recursive call (নাও / বাদ দাও); choose → explore → un-choose দিয়ে একটা shared path-এ 2^n leaf হাঁটা — সব backtracking enumeration-এর মূল কঙ্কাল।

24. Final summary¶

ভবিষ্যতের আমাকে: "Subsets = প্রতিটা item-এ include/exclude দুটো branch; base case-এ path-এর snapshot record করো।" যখনই 'সব সম্ভাব্য combination/সংগ্রহ enumerate করো' বা '2^n' শুনবে — এই include/exclude backtracking skeleton মনে করবে; এটা চোখ বুজে লিখতে পারা চাই।

25. JavaScript solution (with test cases)¶

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 করে।

26. TypeScript solution (with test cases)¶

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<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
const norm = (lol: number[][]): string =>
  JSON.stringify(lol.map(s => [...s].sort((a, b) => a - b))
    .sort((a, b) => JSON.stringify(a).localeCompare(JSON.stringify(b))));

expect(norm(subsets([1, 2, 3])), norm([[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]), "main");
expect(subsets([1, 2, 3]).length, 8, "2^3");
expect(JSON.stringify(subsets([])), JSON.stringify([[]]), "empty");
expect(subsets([1, 2, 3, 4]).length, 16, "2^4");
console.log("সব TS test pass!");

TS টীকা: return type number[][] (number-এর array-র array) স্পষ্ট করে এটা subset-এর collection ফেরায়। path: number[]-কে mutable working buffer হিসেবে পাস করি, আর out.push([...path])-এ copy নেওয়ায় out-এর প্রতিটা element স্বাধীন — কম্পাইলার aliasing-bug ধরতে পারে না, তাই snapshot নেওয়াটা programmer-এর দায়িত্ব, এবং type এখানে সেই pattern স্পষ্ট রাখে।

27. কোথায় কাজে লাগে (real-world use)¶

Feature flag combinations: সব সম্ভাব্য feature on/off সংমিশ্রণ enumerate করে testing/AB-config বানাতে।
Power set / option menus: সব সম্ভাব্য toppings/add-on/filter সংমিশ্রণ তৈরি করতে।
Brute-force search space: ছোট ইনপুটে সব subset যাচাই করে optimal খোঁজা (subset-sum, knapsack baseline)।
Permission/role sets: সম্ভাব্য সব permission-combination বিশ্লেষণ করতে।
Test-case generation: parameter-এর সব subset দিয়ে combinatorial test coverage।

এক কথায়, "সব সম্ভাব্য সংগ্রহ/combination enumerate করো (2^n)" শুনলেই — প্রতি item-এ include/exclude এই backtracking skeleton; এটা প্রায় সব enumeration backtracking-এর মূল কঙ্কাল।

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