Backtracking sounds intimidating. It conjures images of complex algorithms, N-Queens puzzles, and Sudoku solvers — the kind of problems that make you close the tab and re-evaluate your career choices. But here's a secret: **backtracking is just "try everything, but be smart about giving up early."** That's it. Try a choice. See what happens. If it leads to a dead end, undo it and try something else. It's systematic trial and error. Think of it like solving a maze: you walk forward, hit a wall, turn around, go back to the last intersection, and try a different path. You don't start over from the beginning — you just undo your last decision and pick a different one. You've actually been doing backtracking your entire life. Ever tried assembling furniture without the instructions? You try a piece, it doesn't fit, you pull it out, try another. That's backtracking. Ever played 20 Questions? Each question narrows the space, and a "no" makes you back up and think differently. That's backtracking too. In code, backtracking is recursion with a twist: **you modify some state before the recursive call, then undo that modification after the call returns**. The "undo" step is the backtrack. It's what makes this technique different from plain recursion. > "Backtracking is DFS on the tree of choices, with an eraser in hand." And the beautiful part? Once you learn the template, you can solve *dozens* of problems. Permutations, combinations, subsets, word search, Sudoku, N-Queens — they're all the same skeleton with different clothes. This guide will teach you that skeleton, dress it up for every major problem type, and make sure you never freeze when you see a backtracking problem again. Let's go. --- ## The Mental Model: Decision Trees Before you write a single line of backtracking code, you need to see the **decision tree**. Every backtracking problem is a tree of choices, and the algorithm is just a walk through that tree. ### What Is a Decision Tree? A decision tree is a visualization of all the choices you can make at each step, and where each choice leads. Every **node** is a decision point. Every **edge** is a choice. Every **leaf** is either a valid solution or a dead end. Let's make this concrete. Say you want to generate all subsets of `[1, 2, 3]`. At each step, you decide: **include this element, or don't**. ``` [] / \ [1] [] / \ / \ [1,2] [1] [2] [] / \ / \ / \ / \ [1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] [] ``` Every path from root to leaf represents a complete sequence of decisions. The leaves are your subsets: `[1,2,3]`, `[1,2]`, `[1,3]`, `[1]`, `[2,3]`, `[2]`, `[3]`, `[]`. That's 2³ = 8 subsets. Each element has two choices (in or out), and there are 3 elements, so the tree has 2³ leaves. This is the **structure** that backtracking explores. ### The Key Insight **Backtracking = Depth-First Search on the decision tree.** You go deep along one branch, explore it fully, then backtrack to the parent and try the next branch. You never explore a branch that you know is doomed (that's pruning, which we'll cover later). Here's the flow: 1. Start at the root (empty state) 2. Make a choice (go left or right, pick an element, place a queen) 3. Recurse deeper 4. If you reach a valid leaf → record the solution 5. If you reach a dead end → stop, go back up 6. **Undo the choice** (this is the backtrack!) 7. Try the next choice The "undo" in step 6 is everything. Without it, you're just doing DFS. With it, you're doing backtracking — you leave the state exactly as you found it so the next branch starts fresh. > Think of backtracking like reading a "Choose Your Own Adventure" book with a bookmark. You pick a choice, read ahead. If the story ends badly, you flip back to the bookmark and try the other choice. The bookmark is your backtrack point. --- ## The Template: Choose → Explore → Unchoose Here's the universal backtracking template. Memorize it. Internalize it. Tattoo it on your forearm if you have to. Almost every backtracking problem follows this exact structure. ```typescript function backtrack(result: any[], state: any[], choices: any[], start: number): void { // Base case: is the current state a valid solution? if (isSolution(state)) { result.push([...state]); // COPY the state! return; } for (let i = start; i < choices.length; i++) { // 1. CHOOSE — make a decision state.push(choices[i]); // 2. EXPLORE — recurse with the updated state backtrack(result, state, choices, i + 1); // 3. UNCHOOSE — undo the decision (backtrack) state.pop(); } } ``` ### The Three Steps, Explained **Step 1: Choose** — You pick one option from the available choices and modify the current state. This might mean adding an element to a path, placing a queen on a board, or filling in a Sudoku cell. **Step 2: Explore** — You recurse deeper with the modified state. This explores all consequences of the choice you just made. **Step 3: Unchoose** — After the recursive call returns (meaning you've fully explored that branch), you **undo** the choice. Remove the element, take the queen off the board, clear the Sudoku cell. This restores the state for the next iteration of the loop. ### Why Copy the State? Notice the `[...state]` when pushing to the result. This is critical. If you push `state` directly, you're pushing a **reference** to the same array. As backtracking continues and modifies `state`, your "saved" result gets modified too. You end up with a result full of empty arrays. This is the #1 backtracking bug. ```typescript // WRONG — all entries point to the same (eventually empty) array result.push(state); // RIGHT — snapshot the current state result.push([...state]); ``` > This template is your Swiss Army knife. The specific `isSolution` check, the `choices` loop, and the choose/unchoose operations change per problem — but the skeleton stays the same. --- ## The Core Three: Subsets, Permutations, Combinations These three problem families are the bread and butter of backtracking. Master them, and you'll have the intuition to tackle almost anything. --- ### Subsets (LeetCode 78) **Problem:** Given an integer array `nums` of unique elements, return all possible subsets (the power set). **Example:** `nums = [1, 2, 3]` → `[[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]` #### The Decision Tree For subsets, at each element you decide: **include it or skip it**. But it's easier to think of it as: "for each position, try adding each remaining element." ``` backtrack(start=0, current=[]) ├── add 1 → backtrack(start=1, current=[1]) │ ├── add 2 → backtrack(start=2, current=[1,2]) │ │ └── add 3 → backtrack(start=3, current=[1,2,3]) → save [1,2,3] │ │ save [1,2] │ └── add 3 → backtrack(start=3, current=[1,3]) → save [1,3] │ save [1] ├── add 2 → backtrack(start=1, current=[2]) │ └── add 3 → backtrack(start=3, current=[2,3]) → save [2,3] │ save [2] └── add 3 → backtrack(start=2, current=[3]) → save [3] save [] ``` Every node is a valid subset. That's the key difference from permutations — we collect results at **every** node, not just the leaves. #### TypeScript Solution ```typescript function subsets(nums: number[]): number[][] { const result: number[][] = []; function backtrack(start: number, current: number[]): void { result.push([...current]); for (let i = start; i < nums.length; i++) { current.push(nums[i]); backtrack(i + 1, current); current.pop(); } } backtrack(0, []); return result; } ``` Notice there's no explicit base case that returns early. The loop naturally terminates when `start >= nums.length`, because there are no more elements to add. And we push every state to the result — not just complete ones. #### The Iterative Cascading Approach For comparison, here's a completely different way to generate subsets — no recursion at all. Start with `[[]]`, and for each element, add it to every existing subset: ```typescript function subsetsIterative(nums: number[]): number[][] { const result: number[][] = [[]]; for (const num of nums) { const newSubsets = result.map(subset => [...subset, num]); result.push(...newSubsets); } return result; } ``` ``` Start: [[]] Add 1: [[], [1]] Add 2: [[], [1], [2], [1,2]] Add 3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]] ``` Both approaches produce the same result. The iterative version is clever, but the backtracking version generalizes to harder problems (like subsets with constraints). Know both, but rely on backtracking when things get complex. #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n × 2ⁿ) | | Space | O(n) recursion depth | There are 2ⁿ subsets, and copying each one takes up to O(n) time. --- ### Subsets II (LeetCode 90) **Problem:** Given an integer array `nums` that may contain duplicates, return all possible subsets. The solution set must not contain duplicate subsets. **Example:** `nums = [1, 2, 2]` → `[[], [1], [1,2], [1,2,2], [2], [2,2]]` #### The Trick: Sort + Skip Duplicates The issue with duplicates is that `[1, 2a]` and `[1, 2b]` are the same subset when both 2's have the same value. The fix: 1. **Sort** the array first (groups duplicates together) 2. **Skip** an element if it's the same as the previous one *at the same decision level* ```typescript function subsetsWithDup(nums: number[]): number[][] { const result: number[][] = []; nums.sort((a, b) => a - b); function backtrack(start: number, current: number[]): void { result.push([...current]); for (let i = start; i < nums.length; i++) { if (i > start && nums[i] === nums[i - 1]) continue; current.push(nums[i]); backtrack(i + 1, current); current.pop(); } } backtrack(0, []); return result; } ``` The critical line is `if (i > start && nums[i] === nums[i - 1]) continue`. This says: "If I'm not the first choice at this level and my value is the same as the previous choice, skip me." The `i > start` part is important — we only skip when we're looking at siblings in the tree, not when we're going deeper. ``` nums = [1, 2, 2] (sorted) backtrack(0, []) ├── i=0, add 1 → backtrack(1, [1]) │ ├── i=1, add 2 → backtrack(2, [1,2]) │ │ └── i=2, add 2 → backtrack(3, [1,2,2]) → save [1,2,2] │ │ save [1,2] │ └── i=2, nums[2]=2 === nums[1]=2 → SKIP (duplicate at same level) │ save [1] ├── i=1, add 2 → backtrack(2, [2]) │ └── i=2, add 2 → backtrack(3, [2,2]) → save [2,2] │ save [2] └── i=2, nums[2]=2 === nums[1]=2 → SKIP save [] ``` #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n × 2ⁿ) | | Space | O(n) recursion depth | --- ### Permutations (LeetCode 46) **Problem:** Given an array `nums` of distinct integers, return all possible permutations. **Example:** `nums = [1, 2, 3]` → `[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]` #### The Decision Tree For permutations, at each position you pick **any remaining element**. The key difference from subsets: order matters, and every element must be used exactly once. ``` [] / | \ [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] ``` 3 choices at level 1, 2 choices at level 2, 1 choice at level 3 → 3! = 6 permutations. #### TypeScript Solution ```typescript function permute(nums: number[]): number[][] { const result: number[][] = []; function backtrack(current: number[], used: boolean[]): void { 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]); backtrack(current, used); current.pop(); used[i] = false; } } backtrack([], new Array(nums.length).fill(false)); return result; } ``` Notice the differences from subsets: - We use a `used[]` boolean array instead of a `start` index (because any unused element can come next) - We only collect results when `current.length === nums.length` (full permutation) - The loop always starts from 0 (not from `start`), because order matters The `used[i] = true` / `used[i] = false` is the **choose/unchoose** pattern at work. We mark an element as used before recursing, and unmark it after. #### Step-by-Step Trace ``` backtrack([], used=[F,F,F]) ├── i=0: choose 1 → backtrack([1], used=[T,F,F]) │ ├── i=0: used → skip │ ├── i=1: choose 2 → backtrack([1,2], used=[T,T,F]) │ │ ├── i=0: used → skip │ │ ├── i=1: used → skip │ │ └── i=2: choose 3 → backtrack([1,2,3], used=[T,T,T]) │ │ → length === 3, save [1,2,3] │ │ unchoose 3 │ │ unchoose 2 │ └── i=2: choose 3 → backtrack([1,3], used=[T,F,T]) │ └── i=1: choose 2 → backtrack([1,3,2], used=[T,T,T]) │ → save [1,3,2] │ unchoose 1 ├── i=1: choose 2 → ... (builds [2,1,3] and [2,3,1]) └── i=2: choose 3 → ... (builds [3,1,2] and [3,2,1]) ``` #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n × n!) | | Space | O(n) recursion depth | There are n! permutations, and copying each one costs O(n). --- ### Permutations II (LeetCode 47) **Problem:** Given a collection of numbers, `nums`, that might contain duplicates, return all possible unique permutations in any order. **Example:** `nums = [1, 1, 2]` → `[[1,1,2], [1,2,1], [2,1,1]]` #### The Fix: Sort + Skip Duplicates (Again) Same trick as Subsets II. Sort first, then skip a number if it's the same as the previous one **and** the previous one hasn't been used at this level. ```typescript function permuteUnique(nums: number[]): number[][] { const result: number[][] = []; nums.sort((a, b) => a - b); function backtrack(current: number[], used: boolean[]): void { if (current.length === nums.length) { result.push([...current]); return; } for (let i = 0; i < nums.length; i++) { if (used[i]) continue; if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue; used[i] = true; current.push(nums[i]); backtrack(current, used); current.pop(); used[i] = false; } } backtrack([], new Array(nums.length).fill(false)); return result; } ``` The new line is `if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue`. This says: "If the previous duplicate isn't used, skip this one." This forces duplicates to be used in order (first duplicate before second), preventing duplicate permutations. Why `!used[i - 1]` and not `used[i - 1]`? Either works (they just prune different branches), but `!used[i - 1]` prunes more aggressively. It says: "Only use this duplicate if all previous identical values have already been placed." This keeps the duplicates in their original relative order. #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n × n!) worst case | | Space | O(n) | --- ### Combinations (LeetCode 77) **Problem:** Given two integers `n` and `k`, return all possible combinations of `k` numbers chosen from the range `[1, n]`. **Example:** `n = 4, k = 2` → `[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]` #### The Decision Tree Combinations are like subsets, but we only collect results of a specific size `k`. Use a `start` index to avoid duplicates (order doesn't matter in combinations). ``` n=4, k=2 backtrack(start=1, current=[]) ├── add 1 → backtrack(start=2, current=[1]) │ ├── add 2 → [1,2] ✓ (length === k) │ ├── add 3 → [1,3] ✓ │ └── add 4 → [1,4] ✓ ├── add 2 → backtrack(start=3, current=[2]) │ ├── add 3 → [2,3] ✓ │ └── add 4 → [2,4] ✓ ├── add 3 → backtrack(start=4, current=[3]) │ └── add 4 → [3,4] ✓ └── add 4 → backtrack(start=5, current=[4]) → can't pick enough elements, prune ``` #### TypeScript Solution ```typescript function combine(n: number, k: number): number[][] { const result: number[][] = []; function backtrack(start: number, current: number[]): void { if (current.length === k) { result.push([...current]); return; } for (let i = start; i <= n; i++) { current.push(i); backtrack(i + 1, current); current.pop(); } } backtrack(1, []); return result; } ``` #### Pruning Optimization Notice in the decision tree above, when we're at `current = [4]` and need 1 more element, there's nothing left to pick. We can prune earlier: ```typescript function combineOptimized(n: number, k: number): number[][] { const result: number[][] = []; function backtrack(start: number, current: number[]): void { if (current.length === k) { result.push([...current]); return; } const remaining = k - current.length; for (let i = start; i <= n - remaining + 1; i++) { current.push(i); backtrack(i + 1, current); current.pop(); } } backtrack(1, []); return result; } ``` The bound `n - remaining + 1` ensures we only start a branch if there are enough elements left to fill the combination. This avoids exploring doomed subtrees. #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(k × C(n,k)) | | Space | O(k) recursion depth | --- ### Combination Sum (LeetCode 39) **Problem:** Given an array of distinct integers `candidates` and a target integer `target`, return all unique combinations where the candidates sum to `target`. The same number may be chosen an **unlimited number of times**. **Example:** `candidates = [2,3,6,7], target = 7` → `[[2,2,3], [7]]` #### The Key Insight: Allow Repeats The twist here: you can reuse elements. Instead of passing `i + 1` for the next `start`, pass `i` — so the same element can be chosen again. ``` target=7, candidates=[2,3,6,7] backtrack(start=0, current=[], remaining=7) ├── add 2 (rem=5) → backtrack(start=0, current=[2], rem=5) │ ├── add 2 (rem=3) → backtrack(start=0, current=[2,2], rem=3) │ │ ├── add 2 (rem=1) → backtrack(start=0, current=[2,2,2], rem=1) │ │ │ ├── add 2 (rem=-1) → PRUNE (negative) │ │ │ └── ... all too big → dead end │ │ └── add 3 (rem=0) → [2,2,3] ✓ FOUND! │ ├── add 3 (rem=2) → ... no valid combos │ └── ... ├── add 3 (rem=4) → ... no valid combos ├── add 6 (rem=1) → ... no valid combos └── add 7 (rem=0) → [7] ✓ FOUND! ``` #### TypeScript Solution ```typescript function combinationSum(candidates: number[], target: number): number[][] { const result: number[][] = []; function backtrack(start: number, current: number[], remaining: number): void { if (remaining === 0) { result.push([...current]); return; } if (remaining < 0) return; for (let i = start; i < candidates.length; i++) { current.push(candidates[i]); backtrack(i, current, remaining - candidates[i]); // i, not i+1 (allow reuse) current.pop(); } } backtrack(0, [], target); return result; } ``` The subtle change: `backtrack(i, ...)` instead of `backtrack(i + 1, ...)`. This lets us pick the same candidate again. But we still use `start` to prevent generating both `[2,3]` and `[3,2]`. #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n^(target/min)) worst case | | Space | O(target/min) recursion depth | Where `min` is the smallest candidate. In the worst case, we pick the smallest number over and over. --- ### Combination Sum II (LeetCode 40) **Problem:** Given a collection of candidate numbers (`candidates`) and a target number, find all unique combinations in `candidates` where the candidate numbers sum to `target`. Each number may only be used **once**. The solution set must not contain duplicate combinations. **Example:** `candidates = [10,1,2,7,6,1,5], target = 8` → `[[1,1,6], [1,2,5], [1,7], [2,6]]` #### The Familiar Fix: Sort + Skip This combines the ideas from Combination Sum (sum to target) and Subsets II (skip duplicates). ```typescript function combinationSum2(candidates: number[], target: number): number[][] { const result: number[][] = []; candidates.sort((a, b) => a - b); function backtrack(start: number, current: number[], remaining: number): void { if (remaining === 0) { result.push([...current]); return; } if (remaining < 0) return; for (let i = start; i < candidates.length; i++) { if (i > start && candidates[i] === candidates[i - 1]) continue; if (candidates[i] > remaining) break; // pruning: sorted, so all after are too big current.push(candidates[i]); backtrack(i + 1, current, remaining - candidates[i]); current.pop(); } } backtrack(0, [], target); return result; } ``` Two things to note: 1. `i > start && candidates[i] === candidates[i - 1]` — skip duplicates at the same level 2. `candidates[i] > remaining` — since the array is sorted, if the current candidate exceeds the remaining target, all subsequent candidates will too. **Break early.** That `break` is a powerful prune. Without it, you'd keep exploring branches that can never reach the target. #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(2ⁿ) worst case | | Space | O(n) | --- ## String Backtracking Backtracking isn't just for numbers. Strings are a natural fit — you're building a string character by character, exploring all possibilities, and backtracking when you hit a constraint. --- ### Letter Combinations of a Phone Number (LeetCode 17) **Problem:** Given a string containing digits from `2-9`, return all possible letter combinations that the number could represent (like T9 texting). ``` 2 → "abc" 3 → "def" 4 → "ghi" 5 → "jkl" 6 → "mno" 7 → "pqrs" 8 → "tuv" 9 → "wxyz" ``` **Example:** `digits = "23"` → `["ad","ae","af","bd","be","bf","cd","ce","cf"]` #### The Decision Tree Each digit maps to letters. At each level, pick one letter from the current digit's mapping: ``` digits = "23" "" / | \ "a" "b" "c" ← letters for '2' / | \ / | \ / | \ ad ae af bd be bf cd ce cf ← letters for '3' ``` #### TypeScript Solution ```typescript function letterCombinations(digits: string): string[] { if (digits.length === 0) return []; const phoneMap: Record = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' }; const result: string[] = []; function backtrack(index: number, current: string): void { if (index === digits.length) { result.push(current); return; } const letters = phoneMap[digits[index]]; for (const letter of letters) { backtrack(index + 1, current + letter); } } backtrack(0, ''); return result; } ``` Notice we don't need an explicit "unchoose" here because strings are immutable in JavaScript. When we do `current + letter`, we create a new string — we're not mutating `current`. The old value naturally persists for the next iteration. If we were using an array of characters instead, we'd need `push` + `pop`. #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(4ⁿ) where n is the number of digits | | Space | O(n) recursion depth | The worst case is all 7s and 9s (4 letters each), giving 4ⁿ combinations. --- ### Generate Parentheses (LeetCode 22) **Problem:** Given `n` pairs of parentheses, generate all combinations of well-formed parentheses. **Example:** `n = 3` → `["((()))","(()())","(())()","()(())","()()()"]` #### The Decision Tree with Pruning At each position, you can add `(` or `)`. But not all choices are valid — you need constraints: - You can add `(` if you haven't used all `n` opens yet - You can add `)` only if the number of closes is less than the number of opens (so parentheses stay balanced) ``` n = 2 "" / \ "(" ")" ← INVALID (close > open) / \ "((" "()" / / \ "(()" "()(" "())" ← INVALID / | "(())" "()()" ``` This is a classic example of **pruning**. We don't explore branches that violate our constraints. #### TypeScript Solution ```typescript function generateParenthesis(n: number): string[] { const result: string[] = []; function backtrack(current: string, open: number, close: number): void { if (current.length === 2 * n) { result.push(current); return; } if (open < n) { backtrack(current + '(', open + 1, close); } if (close < open) { backtrack(current + ')', open, close + 1); } } backtrack('', 0, 0); return result; } ``` The elegance here is in the pruning conditions. We only have two choices at each step, but the constraints (`open < n` and `close < open`) cut out all invalid branches. No wasted work. #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(4ⁿ / √n) — the n-th Catalan number | | Space | O(n) | --- ### Palindrome Partitioning (LeetCode 131) **Problem:** Given a string `s`, partition `s` such that every substring in the partition is a palindrome. Return all possible palindrome partitionings. **Example:** `s = "aab"` → `[["a","a","b"], ["aa","b"]]` #### The Approach At each step, try all possible prefixes. If the prefix is a palindrome, take it as a partition and recurse on the remaining string. ``` s = "aab" backtrack(start=0, current=[]) ├── "a" is palindrome → backtrack(start=1, current=["a"]) │ ├── "a" is palindrome → backtrack(start=2, current=["a","a"]) │ │ └── "b" is palindrome → save ["a","a","b"] ✓ │ └── "ab" is NOT palindrome → skip ├── "aa" is palindrome → backtrack(start=2, current=["aa"]) │ └── "b" is palindrome → save ["aa","b"] ✓ └── "aab" is NOT palindrome → skip ``` #### TypeScript Solution ```typescript function partition(s: string): string[][] { const result: string[][] = []; function isPalindrome(str: string, left: number, right: number): boolean { while (left < right) { if (str[left] !== str[right]) return false; left++; right--; } return true; } function backtrack(start: number, current: string[]): void { if (start === s.length) { result.push([...current]); return; } for (let end = start; end < s.length; end++) { if (!isPalindrome(s, start, end)) continue; current.push(s.substring(start, end + 1)); backtrack(end + 1, current); current.pop(); } } backtrack(0, []); return result; } ``` The pruning here is the palindrome check. If a prefix isn't a palindrome, we skip it entirely — no need to explore that subtree. #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n × 2ⁿ) worst case | | Space | O(n) | --- ## Grid Backtracking When backtracking meets 2D grids, things get spatial. Instead of choosing from a list, you're choosing directions. Instead of a `used` array, you're marking cells on a board. --- ### Word Search (LeetCode 79) **Problem:** Given an `m x n` grid of characters and a string `word`, return `true` if `word` exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically). The same cell may not be used more than once. **Example:** ``` board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCCED" → true word = "SEE" → true word = "ABCB" → false ``` #### The Approach For each cell that matches the first letter, start a DFS. At each step: 1. Check if the current cell matches the current letter 2. Mark the cell as visited (choose) 3. Explore all 4 neighbors 4. Unmark the cell (unchoose) The "marking visited" and "unmarking" is the backtracking. You can't reuse cells within one path, but you need them available for other paths. #### TypeScript Solution ```typescript function exist(board: string[][], word: string): boolean { const rows = board.length; const cols = board[0].length; const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]; function backtrack(row: number, col: number, index: number): boolean { if (index === word.length) return true; if ( row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] !== word[index] ) { return false; } const temp = board[row][col]; board[row][col] = '#'; // mark as visited (choose) for (const [dr, dc] of directions) { if (backtrack(row + dr, col + dc, index + 1)) { board[row][col] = temp; // restore before returning return true; } } board[row][col] = temp; // unmark (unchoose) return false; } for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (backtrack(r, c, 0)) return true; } } return false; } ``` Instead of a separate `visited` array, we mutate the board directly — setting the cell to `'#'` so it won't match any letter. This is a common trick for grid backtracking problems. After the recursive call returns, we restore the original value. #### Visual Walkthrough Searching for "ABCCED" on the example board: ``` Step 1: Start at (0,0)='A' ✓ A* B C E (* = current path) S F C S A D E E Step 2: Move right to (0,1)='B' ✓ A* B* C E S F C S A D E E Step 3: Move right to (0,2)='C' ✓ A* B* C* E S F C S A D E E Step 4: Move down to (1,2)='C' ✓ A* B* C* E S F C* S A D E E Step 5: Move down to (2,2)='E' ✓ A* B* C* E S F C* S A D E* E Step 6: Move left to (2,1)='D' ✓ → Found "ABCCED"! ``` #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(m × n × 3^L) where L is word length | | Space | O(L) recursion depth | Why 3^L and not 4^L? Because at each step (except the first), we came from one direction, so we only have 3 unexplored directions. --- ### N-Queens (LeetCode 51) **Problem:** Place `n` queens on an `n × n` chessboard such that no two queens threaten each other (same row, column, or diagonal). Return all distinct solutions. This is *the* classic backtracking problem. It's been studied for over 150 years, and it's still a favorite in interviews. #### The Approach Place queens one row at a time (row 0, then row 1, etc.). For each row, try every column. Before placing, check if it conflicts with already-placed queens. If it does, skip. If it doesn't, place and recurse to the next row. The constraint tracking is the interesting part. We need to know which columns and diagonals are already under attack. A queen attacks: - Its **column** - Its **main diagonal** (top-left to bottom-right): all cells where `row - col` is the same - Its **anti-diagonal** (top-right to bottom-left): all cells where `row + col` is the same We use three sets to track which columns, diagonals, and anti-diagonals are occupied. #### Visual: 4-Queens Solution Let's trace finding one solution for n=4: ``` Step 1: Place Q at (0,1) Step 2: Place Q at (1,3) . Q . . . Q . . . . . . . . . Q . . . . . . . . . . . . . . . . Step 3: Place Q at (2,0) Step 4: Place Q at (3,2) Q . . . . Q . . . . . Q . . . Q Q . . . ← (2,0) Q . . . . . . . . . Q . ← Solution found! ``` One of the two valid 4-Queens solutions: `[".Q..","...Q","Q...","..Q."]` #### TypeScript Solution ```typescript function solveNQueens(n: number): string[][] { const result: string[][] = []; const cols = new Set(); const diags = new Set(); // row - col const antiDiags = new Set(); // row + col const board: string[][] = Array.from({ length: n }, () => Array(n).fill('.')); function backtrack(row: number): void { if (row === n) { result.push(board.map(r => r.join(''))); return; } for (let col = 0; col < n; col++) { if (cols.has(col) || diags.has(row - col) || antiDiags.has(row + col)) { continue; } board[row][col] = 'Q'; cols.add(col); diags.add(row - col); antiDiags.add(row + col); backtrack(row + 1); board[row][col] = '.'; cols.delete(col); diags.delete(row - col); antiDiags.delete(row + col); } } backtrack(0); return result; } ``` The choose/unchoose pattern here has four operations each way — updating the board and the three constraint sets. That's more bookkeeping than simpler problems, but the structure is identical. #### Why Sets for Diagonals? The diagonal trick is elegant. On a main diagonal (↘), `row - col` is constant. On an anti-diagonal (↙), `row + col` is constant. So checking if a diagonal is occupied is just a set lookup — O(1). ``` Main diagonals (row - col): Anti-diagonals (row + col): 0 -1 -2 -3 0 1 2 3 1 0 -1 -2 1 2 3 4 2 1 0 -1 2 3 4 5 3 2 1 0 3 4 5 6 ``` Same number = same diagonal. Simple and fast. #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n!) — with pruning, much less in practice | | Space | O(n²) for the board | --- ### Sudoku Solver (LeetCode 37) **Problem:** Write a program to solve a Sudoku puzzle by filling the empty cells. Each row, column, and 3×3 box must contain digits 1-9 with no repetition. This is constraint satisfaction at its finest. Try a number, check constraints, recurse. If stuck, backtrack. #### The Approach 1. Find the next empty cell 2. Try digits 1-9 3. For each digit, check if placing it is valid (no conflict in row, column, or 3×3 box) 4. If valid, place and recurse 5. If recursion fails, remove the digit and try the next one 6. If no digit works, return false (triggers backtracking to the previous cell) #### TypeScript Solution ```typescript function solveSudoku(board: string[][]): void { solve(board); } function solve(board: string[][]): boolean { for (let row = 0; row < 9; row++) { for (let col = 0; col < 9; col++) { if (board[row][col] !== '.') continue; for (let num = 1; num <= 9; num++) { const char = String(num); if (isValid(board, row, col, char)) { board[row][col] = char; if (solve(board)) return true; board[row][col] = '.'; // backtrack } } return false; // no valid number for this cell → backtrack } } return true; // all cells filled } function isValid(board: string[][], row: number, col: number, char: string): boolean { for (let i = 0; i < 9; i++) { if (board[row][i] === char) return false; if (board[i][col] === char) return false; const boxRow = 3 * Math.floor(row / 3) + Math.floor(i / 3); const boxCol = 3 * Math.floor(col / 3) + (i % 3); if (board[boxRow][boxCol] === char) return false; } return true; } ``` #### The `return false` That Makes It Work The line `return false` after trying all 9 digits is crucial. It means: "I tried every number for this empty cell and nothing worked. This board state is unsolvable." This `false` propagates back up the call stack, causing the previous cell to try its next option. This is different from the subset/permutation problems where we always find solutions. In Sudoku, some paths genuinely lead to dead ends, and we need to communicate that failure back up. #### Optimized Version with Set-Based Tracking The above solution rechecks constraints from scratch each time. We can speed it up by maintaining sets: ```typescript function solveSudokuOptimized(board: string[][]): void { const rowSets: Set[] = Array.from({ length: 9 }, () => new Set()); const colSets: Set[] = Array.from({ length: 9 }, () => new Set()); const boxSets: Set[] = Array.from({ length: 9 }, () => new Set()); const emptyCells: [number, number][] = []; for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { if (board[r][c] === '.') { emptyCells.push([r, c]); } else { const val = board[r][c]; rowSets[r].add(val); colSets[c].add(val); boxSets[getBoxIndex(r, c)].add(val); } } } function getBoxIndex(row: number, col: number): number { return Math.floor(row / 3) * 3 + Math.floor(col / 3); } function solve(idx: number): boolean { if (idx === emptyCells.length) return true; const [row, col] = emptyCells[idx]; const box = getBoxIndex(row, col); for (let num = 1; num <= 9; num++) { const char = String(num); if (rowSets[row].has(char) || colSets[col].has(char) || boxSets[box].has(char)) { continue; } board[row][col] = char; rowSets[row].add(char); colSets[col].add(char); boxSets[box].add(char); if (solve(idx + 1)) return true; board[row][col] = '.'; rowSets[row].delete(char); colSets[col].delete(char); boxSets[box].delete(char); } return false; } solve(0); } ``` This version pre-collects empty cells and uses sets for O(1) constraint checking, making it significantly faster for hard puzzles. #### Complexity | Metric | Complexity | |--------|-----------| | Time | O(9^m) where m is the number of empty cells | | Space | O(m) recursion depth | In practice, pruning makes it *much* faster than the theoretical worst case. Most Sudoku puzzles are solved in milliseconds. --- ## Pruning: The Art of Giving Up Early We've seen pruning in several problems already, but let's formalize it. **Pruning** is the practice of cutting off branches of the decision tree early when you can prove they'll never lead to a valid solution. Without pruning, backtracking is just brute force. With pruning, it's intelligent search. ### Why Pruning Matters Consider N-Queens for n=8. Without any pruning, you'd explore 8⁸ = 16,777,216 board configurations. With column/diagonal pruning, the actual number of nodes explored drops to around 15,720 — a reduction of over **99.9%**. ``` N-Queens (n=8): Without pruning: ~16,777,216 nodes With pruning: ~15,720 nodes Reduction: 99.9% ``` That's not a minor optimization. It's the difference between a solution that runs in milliseconds and one that takes minutes. ### Common Pruning Strategies #### 1. Constraint Checking Before Choosing The most basic form of pruning: before making a choice, verify it doesn't violate any constraints. ```typescript // N-Queens: skip invalid columns immediately for (let col = 0; col < n; col++) { if (cols.has(col) || diags.has(row - col) || antiDiags.has(row + col)) { continue; // PRUNE — don't even enter this branch } // ... explore } ``` This is "look before you leap." Don't enter a branch if you already know it's invalid. #### 2. Sorting to Enable Early Termination When choices are sorted, you can break early as soon as a condition is exceeded. ```typescript // Combination Sum II: sorted candidates candidates.sort((a, b) => a - b); for (let i = start; i < candidates.length; i++) { if (candidates[i] > remaining) break; // all subsequent are larger too // ... } ``` Without sorting, you'd have to check every candidate. With sorting, one comparison lets you skip all remaining candidates. #### 3. Bounding (Branch and Bound) Estimate the best-case outcome for a branch. If even the best case isn't good enough, prune it. ```typescript // Combinations: don't start a branch if not enough elements remain const remaining = k - current.length; if (nums.length - i < remaining) break; // can't possibly fill k slots ``` This is common in optimization problems where you're looking for the best solution, not all solutions. You maintain a "best so far" bound and prune any branch that can't possibly beat it. #### 4. Symmetry Breaking If the problem has symmetry, only explore one representative from each symmetric group. For N-Queens, the first queen only needs to go in columns 0 through n/2 — the other half are mirror images. This cuts the search space roughly in half. ### The Pruning Mindset > The goal of pruning isn't to be clever. It's to avoid doing work you know is wasted. Every constraint you can check *before* entering a branch saves you from exploring an entire subtree. When approaching a backtracking problem, always ask: 1. What makes a choice invalid? Check that *before* choosing. 2. Can I sort to enable early termination? 3. Can I calculate a bound to eliminate hopeless branches? 4. Is there symmetry I can exploit? --- ## Backtracking vs DFS vs Recursion These three terms get thrown around interchangeably, and that causes confusion. Let's untangle them. ### Recursion **Recursion** is a *technique* — a function calling itself. It's the broadest category. Factorial, Fibonacci, tree traversals — these are all recursive, but they're not backtracking. ```typescript // Recursion, not backtracking function factorial(n: number): number { if (n <= 1) return 1; return n * factorial(n - 1); } ``` No choices being explored. No state being undone. Just recursion. ### DFS (Depth-First Search) **DFS** is a *traversal strategy* — explore as deep as possible before backtracking. It's typically used on trees and graphs. DFS is *implemented* with recursion (or a stack), but the focus is on the traversal order. ```typescript // DFS on a tree — visit all nodes function dfs(node: TreeNode | null): void { if (!node) return; console.log(node.val); dfs(node.left); dfs(node.right); } ``` This visits every node, but there's no "choice" being explored or undone. ### Backtracking **Backtracking** is DFS on a *decision tree* with the added step of *undoing choices*. It's DFS + the choose/unchoose pattern. ```typescript // Backtracking: DFS + undo function backtrack(state, choices) { if (isSolution(state)) { record(state); return; } for (const choice of choices) { state.push(choice); // choose backtrack(state, next); // explore (DFS) state.pop(); // unchoose (backtrack) } } ``` ### The Relationship ``` ┌───────────────────────────────────┐ │ Recursion │ │ ┌─────────────────────────────┐ │ │ │ DFS │ │ │ │ ┌───────────────────────┐ │ │ │ │ │ Backtracking │ │ │ │ │ │ (DFS + undo state) │ │ │ │ │ └───────────────────────┘ │ │ │ └─────────────────────────────┘ │ └───────────────────────────────────┘ ``` - All backtracking uses DFS (you go deep first) - All DFS uses recursion (or an explicit stack) - But not all recursion is DFS, and not all DFS is backtracking - **Backtracking = DFS + state modification + undo** The undo step is the defining feature. If you're not undoing state, you're doing DFS, not backtracking. --- ## Pattern Recognition: When to Think Backtracking Backtracking problems have telltale signs. Learn to spot them and you'll know your approach before you even write code. ### Signal Words in the Problem | Signal | Example | |--------|---------| | "Generate all..." | Generate all permutations | | "Find all possible..." | Find all possible combinations | | "List every..." | List every valid configuration | | "All combinations/permutations" | Return all combinations that sum to target | | "All valid..." | All valid parentheses strings | | Constraint satisfaction | Sudoku, N-Queens, crossword puzzles | ### The Decision Framework Ask yourself these questions: 1. **Is the problem asking for ALL solutions, not just one or the count?** → Strong backtracking signal. (If you just need the count, DP might be better.) 2. **Can I model the problem as a sequence of choices?** → If yes, you can build a decision tree. 3. **Do choices have constraints?** → Constraints enable pruning, which makes backtracking efficient. 4. **Is the search space finite?** → Backtracking explores a bounded tree; infinite spaces need other approaches. 5. **Does order matter or not?** → Determines whether you use a `start` index (combinations/subsets) or a `used` array (permutations). ### The Pattern Map | Problem Type | Key Technique | Template Feature | |---|---|---| | Subsets | Include/exclude each element | `start` index, collect at every node | | Permutations | Pick any unused element | `used[]` array, collect at leaves | | Combinations | Pick k from n | `start` index, collect when `length === k` | | Partition/Split | Try all split points | Loop over prefix lengths | | Grid search | Try all 4 directions | Mark/unmark visited cells | | Constraint satisfaction | Try values, check constraints | Return `false` to trigger backtrack | --- ## Common Pitfalls Backtracking bugs are sneaky. The logic usually *looks* right, but one subtle mistake produces wrong results. Here are the most common traps. ### 1. Forgetting to Unchoose This is the #1 most common backtracking bug. You make a choice but forget to undo it. ```typescript // BUG: no unchoose step for (let i = start; i < nums.length; i++) { current.push(nums[i]); backtrack(i + 1, current); // missing: current.pop(); } ``` The state accumulates across branches, and everything breaks. Always pair every `push` with a `pop`, every `add` with a `delete`, every `true` with a `false`. ### 2. Not Copying State When Saving Results ```typescript // BUG: saves a reference, not a copy if (isSolution(current)) { result.push(current); // WRONG — current will be mutated later } // FIX: snapshot the state if (isSolution(current)) { result.push([...current]); // RIGHT — creates an independent copy } ``` This is the second most common bug. All your results end up being the same (usually empty) array. ### 3. Wrong Start Index ```typescript // BUG: always starting from 0 when you want combinations (no duplicates) for (let i = 0; i < nums.length; i++) { // should be i = start // ... } ``` Starting from 0 gives you permutations, not combinations. If order doesn't matter, use a `start` index to only consider elements after the current one. ### 4. Not Sorting Before Dedup ```typescript // BUG: skip condition won't work without sorting if (i > start && nums[i] === nums[i - 1]) continue; // This assumes duplicates are adjacent — only true if sorted! ``` Always sort the input before using the `nums[i] === nums[i - 1]` skip technique. ### 5. Modifying Shared Data Structures ```typescript // BUG: modifying the input array for visited tracking // without restoring it (or restoring at the wrong time) board[row][col] = '#'; // ... recurse ... // forgot to restore: board[row][col] = original; ``` When using the input structure as your "visited" marker, always restore it — even on early returns. ### Debugging Checklist When your backtracking solution produces wrong results: - [ ] Is every choose paired with an unchoose? - [ ] Am I copying state when adding to results (`[...state]`)? - [ ] Am I using the right loop start (0 for permutations, `start` for combinations)? - [ ] Did I sort before applying the duplicate skip? - [ ] Am I mutating shared state and forgetting to restore? - [ ] Does my base case correctly identify valid solutions? - [ ] Am I passing the right index/remaining value to the recursive call? --- ## Cheat Sheet ### The Universal Template ```typescript function backtrack(state, choices, start) { if (isSolution(state)) { result.push([...state]); return; } for (let i = start; i < choices.length; i++) { if (shouldSkip(i)) continue; // prune state.push(choices[i]); // choose backtrack(state, choices, nextStart); // explore state.pop(); // unchoose } } ``` ### Problem → Template Mapping | Problem | Base Case | Loop Start | Recurse With | Dedup | |---|---|---|---|---| | Subsets | collect all | `start` | `i + 1` | sort + skip | | Permutations | `len === n` | `0` | `used[]` | sort + skip | | Combinations | `len === k` | `start` | `i + 1` | sort + skip | | Combo Sum | `rem === 0` | `start` | `i` (reuse) | sort + break | | Combo Sum II | `rem === 0` | `start` | `i + 1` | sort + skip | | Palindrome Part. | `start === n` | `start` | `end + 1` | palindrome check | | N-Queens | `row === n` | `0` (cols) | `row + 1` | col/diag sets | | Sudoku | all filled | `1..9` | next empty | row/col/box sets | ### Decision Tree Shapes ``` SUBSETS: Every node is a result Branching: include each remaining element Shape: wide, shallow PERMUTATIONS: Only leaves are results Branching: pick any unused element Shape: wide at top, narrowing (n, n-1, n-2, ...) COMBINATIONS: Nodes at depth k are results Branching: pick from remaining elements Shape: like subsets, but pruned at depth k ``` ### Pruning Checklist - [ ] Check constraints before choosing (not after) - [ ] Sort input to enable early `break` - [ ] Skip duplicates: `i > start && arr[i] === arr[i-1]` - [ ] Bound check: can we still reach a valid solution from here? - [ ] Use sets for O(1) constraint lookups (N-Queens, Sudoku) ### Complexity Quick Reference | Problem | Time | Space | |---|---|---| | Subsets | O(n × 2ⁿ) | O(n) | | Subsets II | O(n × 2ⁿ) | O(n) | | Permutations | O(n × n!) | O(n) | | Permutations II | O(n × n!) | O(n) | | Combinations | O(k × C(n,k)) | O(k) | | Combo Sum | O(n^(T/min)) | O(T/min) | | Phone Letters | O(4ⁿ) | O(n) | | Parentheses | O(4ⁿ/√n) | O(n) | | Palindrome Part. | O(n × 2ⁿ) | O(n) | | Word Search | O(m × n × 3^L) | O(L) | | N-Queens | O(n!) | O(n²) | | Sudoku | O(9^m) | O(m) | --- ## What's Next You now have a comprehensive toolkit for backtracking. You understand the decision tree mental model, the choose-explore-unchoose template, and how to apply it to subsets, permutations, combinations, string problems, grid problems, and constraint satisfaction puzzles. You know how to prune, how to handle duplicates, and how to debug when things go wrong. But the journey doesn't end here. Backtracking connects to several deeper topics: - **Depth-First Search (DFS) and Breadth-First Search (BFS)** — Backtracking is DFS on a decision tree. When you move to graph algorithms, you'll use the same traversal patterns on actual graph structures — adjacency lists, visited sets, and cycle detection. - **Dynamic Programming** — Many problems that *can* be solved with backtracking can be solved *faster* with DP. If you notice overlapping subproblems in your decision tree (the same subproblem being solved multiple times), that's your cue to reach for memoization or tabulation. - **Greedy Algorithms** — If a problem has the "greedy choice property" (making the locally optimal choice leads to a globally optimal solution), you don't need to backtrack at all. Greedy is backtracking without the "back" — you commit to each choice. - **Graph Algorithms** — Word search was your first taste of backtracking on a grid. Graph traversals extend this to arbitrary structures — finding paths, detecting cycles, topological sorting. Each of these topics gets its own "Made Simple" article. The patterns stack on each other, and the recursive thinking + decision tree model you built here is the foundation they all rest on. > "Backtracking is the art of organized regret — systematically trying every path and knowing exactly when to turn back." Keep practicing. The more decision trees you draw, the more problems you model as choices, the more natural this becomes. Start with the Core Three (subsets, permutations, combinations), then tackle the grid problems, then the constraint satisfaction puzzles. Before long, you'll see a problem description that says "find all..." and your brain will instantly light up: *that's backtracking*. --- ## Thanks for Reading! If this guide helped backtracking click for you, share it with a friend who's stuck on the "find all combinations" LeetCode problems. The best way to solidify your understanding is to explain it to someone else — and if they get confused, well... you can always backtrack and try explaining it a different way. Keep building. Keep solving. You've got this. **Your Dev Brain, Now Thinking in Decision Trees** ---

Problem Solving Patterns: Backtracking, Made Simple