🗓️ Day 17: Backtracking

🧠 Concept Deep Dive

Backtracking is a refined brute-force technique that builds solutions incrementally and abandons ("backtracks") a path as soon as it determines that it won't lead to a valid or optimal solution.

It is commonly used for:

Combinatorics (e.g. permutations, subsets)
Constraint satisfaction (e.g. Sudoku, N-Queens)
Searching all possible valid states

🔁 General Pattern

A backtracking algorithm explores all possible choices at each step and makes decisions recursively:

function backtrack(path: PathType, options: OptionType[]): void {
  if (baseCase(path)) {
    results.push(copyOf(path));
    return;
  }

  for (let option of options) {
    if (!isValid(option)) continue;

    path.push(option);       // make choice
    backtrack(path, options); // explore further
    path.pop();              // undo choice (backtrack)
  }
}

🧹 You “try something,” and if it doesn't work out, undo it and try another path.

🔮 Key Principles

Build partial solutions
Use recursion to explore future choices
Use constraints to prune invalid branches early
Always undo your choice (clean state for next try)

📦 Example 1: Generate All Subsets

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

  function backtrack(start: number, path: number[]) {
    res.push([...path]);  // save current subset

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);           // choose
      backtrack(i + 1, path);       // explore
      path.pop();                   // unchoose
    }
  }

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

🔎 Example:

Input: [1,2]
Output: [[], [1], [2], [1,2]]

🤩 Example 2: Permutations

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

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

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;

      path.push(nums[i]);
      used[i] = true;
      backtrack(path, used);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([], Array(nums.length).fill(false));
  return res;
}

🔎 Example:

Input: [1,2]
Output: [[1,2],[2,1]]

📐 Real-world Analogy

Imagine solving a maze:

You choose a path (recursive call)
If you hit a dead end, you backtrack and try another path
You continue until you find all valid exits or the best one

📊 Time Complexity

Backtracking often explores all possible combinations, so time complexity is typically exponential:

Problem Type	Time Complexity
Subsets (size n)	O(2ⁿ)
Permutations (n!)	O(n × n!)
N-Queens	O(N!)

⚠️ Common Pitfalls

Not undoing state (forgetting to pop/restore)
Reusing options when they're not allowed (no used[] flag)
Ignoring constraints (e.g. repeated elements in permutations)

🏋️ LeetCode-Style Homework

Problem: Letter Combinations of a Phone Number

Write a function to return all letter combinations that the number could represent.

function letterCombinations(digits: string): string[] {
  if (!digits) return [];
  const map: Record<string, string[]> = {
    "2": ["a", "b", "c"],
    "3": ["d", "e", "f"],
    "4": ["g", "h", "i"],
    "5": ["j", "k", "l"],
    "6": ["m", "n", "o"],
    "7": ["p", "q", "r", "s"],
    "8": ["t", "u", "v"],
    "9": ["w", "x", "y", "z"]
  };

  const res: string[] = [];

  function backtrack(index: number, path: string) {
    if (path.length === digits.length) {
      res.push(path);
      return;
    }

    for (let letter of map[digits[index]]) {
      backtrack(index + 1, path + letter);
    }
  }

  backtrack(0, "");
  return res;
}

🔎 Example

Input: "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

🧠 Summary

Backtracking explores all possible paths
Prune invalid choices early using constraints
Clean up your state when backtracking
Use backtracking to solve recursive combinatorics problems

⏯️ Up Next

▶️ Day 18: Memoization & DP Intro