Pattern #9 — Subsets 🎛️

Pattern #9 — Subsets 🎛️

This pattern is about generating all possible combinations of a set of things. It's the foundation for a lot of "generate everything" problems.

1. The Idea (in one line)

For each element, you make a choice: include it, or don't. All those choices together produce every subset.

   Real-life analogy 🍕
   ────────────────────
   Making a pizza with toppings {cheese, mushroom, olive}.
   For EACH topping you decide yes/no. All combinations of
   yes/no give you every possible pizza — including the plain
   one (all "no") and the loaded one (all "yes").

2. The Picture — Building Subsets Step by Step

   Set: [1, 2, 3]

   Start with just the empty subset:   [ [] ]

   Add 1 → take every existing subset, also make a copy WITH 1:
   [ []      [1] ]

   Add 2 → copy each, add 2:
   [ []  [1]      [2]  [1,2] ]

   Add 3 → copy each, add 3:
   [ []  [1]  [2]  [1,2]      [3]  [1,3]  [2,3]  [1,2,3] ]

   👉 8 subsets = 2³. Each element doubles the count (in/out).

3. 🔍 How to SPOT This Pattern

   Use Subsets when you see:
   ✅ "all subsets", "power set"
   ✅ "all combinations"
   ✅ "generate all possible ..."
   ✅ The answer is a LIST OF LISTS (many results, not one number)

4. The Two Ways to Do It

   A) ITERATIVE (build up, like the picture above)
      Start with [[]]. For each number, duplicate all current
      subsets and add the number to the copies.

   B) RECURSIVE / BACKTRACKING (the "choice tree")
      At each element: branch into "include it" and "skip it".
      This connects directly to Pattern #11 (Backtracking).

5. The Code Templates 📝

   // A) Iterative
   function subsets(nums) {
     let result = [[]];
     for (const num of nums) {
       const copies = result.map(sub => [...sub, num]);  // add num
       result = result.concat(copies);
     }
     return result;
   }

   // B) Recursive (backtracking style)
   function subsetsRec(nums) {
     const result = [];
     function backtrack(start, current) {
       result.push([...current]);            // every path is a subset
       for (let i = start; i < nums.length; i++) {
         current.push(nums[i]);              // choose
         backtrack(i + 1, current);          // explore
         current.pop();                       // un-choose (backtrack)
       }
     }
     backtrack(0, []);
     return result;
   }

6. Practice Problems

   ⭐ core
   • Subsets
   • Subsets II (with duplicates — skip repeats)

   ⭐⭐ Medium
   • Combinations (choose k of n)
   • Combination Sum
   • Letter Combinations of a Phone Number
   • Generate Parentheses

7. ⚠️ Common Mistake

   ❌ Pushing `current` directly instead of a COPY `[...current]`.
      Since you keep mutating `current`, all your saved subsets
      would end up pointing to the same (final) array. Always
      store a copy.

Key Takeaway

   Subsets = for each item, "in or out". n items → 2ⁿ subsets.
   Build them iteratively (double each time) or recursively
   (a choice tree). The base skill for all "generate everything"
   problems.

Next: Pattern #10 — Greedy, making the best local choice at each step. 🤑