Pattern #11 — Backtracking 🧭

Pattern #11 — Backtracking 🧭

Backtracking is how you explore every possibility in a smart way — try a choice, go deeper, and if it doesn't work out, undo it and try the next one.

1. The Idea (in one line)

Try a choice → explore where it leads → if it fails or finishes, undo it and try the next choice.

   Real-life analogy 🧩 (a maze)
   ─────────────────────────────
   You're in a maze. At each fork you pick a path. If you hit a
   dead end, you WALK BACK to the last fork and try a different
   path. You keep doing this until you find the exit (or try
   everything). That "walk back and try another" = backtracking.

2. The Picture — a Choice Tree

   Permutations of [1, 2, 3]:

                     start []
        ┌──────────────┼──────────────┐
      [1]            [2]            [3]
     ┌──┴──┐        ┌──┴──┐        ┌──┴──┐
   [1,2] [1,3]   [2,1] [2,3]   [3,1] [3,2]
     │     │        │     │        │     │
  [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]  ← 6 results

   At each level: pick a number not used yet, go down,
   then "un-pick" it and try the next. 🎯

3. The Magic Three Steps (memorize this)

   for each choice:
     1. CHOOSE      → make the choice (add to current)
     2. EXPLORE     → recurse deeper
     3. UN-CHOOSE   → undo the choice (remove it)  ← the "backtrack"!

   That un-choose step is what lets you reuse the same slot
   for the next option.

4. 🔍 How to SPOT This Pattern

   Use Backtracking when you see:
   ✅ "all permutations", "all combinations", "all paths"
   ✅ "generate every valid ..."
   ✅ "N-Queens", "Sudoku solver", "word search"
   ✅ You must EXPLORE choices, and some choices are invalid
      (so you prune / abandon them early).

5. The Code Template 📝 (the universal skeleton)

   function backtrack(current, choices) {
     if (isComplete(current)) {
       result.push([...current]);   // save a COPY
       return;
     }
     for (const choice of choices) {
       if (!isValid(choice)) continue;  // prune invalid choices

       current.push(choice);        // 1. CHOOSE
       backtrack(current, remainingChoices);  // 2. EXPLORE
       current.pop();               // 3. UN-CHOOSE (backtrack)
     }
   }

   // Concrete: all permutations
   function permute(nums) {
     const result = [], used = new Array(nums.length).fill(false);
     function go(current) {
       if (current.length === nums.length) { result.push([...current]); return; }
       for (let i = 0; i < nums.length; i++) {
         if (used[i]) continue;
         used[i] = true; current.push(nums[i]);   // choose
         go(current);                             // explore
         used[i] = false; current.pop();          // un-choose
       }
     }
     go([]);
     return result;
   }

6. Practice Problems

   ⭐ core
   • Permutations
   • Combinations
   • Subsets (yes, backtracking does this too!)

   ⭐⭐ Medium / Hard
   • Combination Sum
   • Generate Parentheses
   • Word Search
   • N-Queens
   • Sudoku Solver

7. ⚠️ Common Mistake

   ❌ Forgetting the UN-CHOOSE step (the pop). Without it, your
      "current" keeps growing and choices leak between branches.
   ❌ Saving `current` instead of a copy `[...current]` (same bug
      as Subsets — all results end up identical).

Key Takeaway

   Backtracking = choose → explore → un-choose. It walks the
   entire tree of possibilities but prunes dead ends early. The
   engine behind permutations, N-Queens, Sudoku, and any
   "generate all valid solutions" problem.

Next: Pattern #12 — Dynamic Programming, the famous one. We'll make it genuinely simple. 🧠