🗓️ Day 28: Subsets and Power Set

🧠 Concept Deep Dive

A subset is any selection of elements from a set, including the empty set and the set itself. The power set is the collection of all subsets.

This is another classic use-case for backtracking and bit manipulation. You can:

Use recursion to explore inclusion/exclusion of each element.
Or use bitmasks to represent subset membership.

🎯 Visual Intuition (Subset Tree)

Input: [1, 2, 3]

           []
         /    \
       1        X
     /   \     \
   2     X      2
  / \     \    / \
 3   X     3  3   X

Each level chooses to include or exclude the current element.

🛠️ Key Patterns

🔁 Backtracking (Include or Not Include)

function subsets(nums: number[]): number[][] {
  const res: number[][] = [];

  function backtrack(index: number, path: number[]) {
    if (index === nums.length) {
      res.push([...path]);
      return;
    }

    // Include nums[index]
    path.push(nums[index]);
    backtrack(index + 1, path);
    path.pop();

    // Exclude nums[index]
    backtrack(index + 1, path);
  }

  backtrack(0, []);
  return res;
}

⚙️ Bitmasking (Power Set)

function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  const n = nums.length;

  for (let mask = 0; mask < (1 << n); mask++) {
    const subset: number[] = [];
    for (let i = 0; i < n; i++) {
      if ((mask & (1 << i)) !== 0) {
        subset.push(nums[i]);
      }
    }
    res.push(subset);
  }

  return res;
}

📘 Example

Input: [1,2,3]

Output:

[
 [], [1], [2], [3],
 [1,2], [1,3], [2,3],
 [1,2,3]
]

🧪 Homework

Generate all subsets of [1,2,3]

function subsets(nums: number[]): number[][] {
  // your code
}

Try to write the same logic using bitmasking.

function subsets(nums: number[]): number[][] {
  // your code
}

🧠 Big-O Cheat Sheet

Time Complexity: O(2^n) — all possible subsets
Space Complexity: O(n) for recursion, O(2^n) output

🔮 Up Next

▶️ Day 29: Word Break with DP + Trie