Backtracking Complete Guide

Algorithm • hard

Backtracking explores a decision tree by trying choices, recursing, then undoing choices when constraints fail.

It is essential for permutation/combination/search problems with combinatorial explosion.

Performance depends heavily on pruning and candidate ordering.

Typical Complexity Baseline

Metric	Value
Complexity Note 1	Often exponential in worst case

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Backtracking try, recurse, undo

Failed branches are pruned (✕) so we do not waste work below them.

Step 1/9Start at ∅. Try each choice; recurse; undo on failure.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Solve ANY Backtracking Problem on Leetcode

Channel: Bitflip

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Decision tree

What it is Implicit tree of candidate choices.

Why it matters Decision tree is a required building block for understanding how Backtracking stays correct and performant on large inputs.

State

What it is Current partial solution.

Why it matters State is a required building block for understanding how Backtracking stays correct and performant on large inputs.

Choice set

What it is Available next options from current state.

Why it matters Choice set is a required building block for understanding how Backtracking stays correct and performant on large inputs.

Constraint check

What it is Pruning condition to stop invalid branches early.

Why it matters Constraint check is a required building block for understanding how Backtracking stays correct and performant on large inputs.

Undo step

What it is Revert state after recursive call returns.

Why it matters Undo step is a required building block for understanding how Backtracking stays correct and performant on large inputs.

Pruning

What it is Discard branch that cannot lead to valid/optimal solution.

Why it matters Discard branch that cannot lead to valid/optimal solution. In Backtracking, this definition helps you reason about correctness and complexity when inputs scale.

Branching factor

What it is Average number of child choices per level.

Why it matters Average number of child choices per level. In Backtracking, this definition helps you reason about correctness and complexity when inputs scale.

Depth

What it is Number of choices made so far.

Why it matters Number of choices made so far. In Backtracking, this definition helps you reason about correctness and complexity when inputs scale.

Constraint propagation

What it is Update remaining options based on recent choices.

Why it matters Update remaining options based on recent choices. In Backtracking, this definition helps you reason about correctness and complexity when inputs scale.

Search tree

What it is Tree of partial configurations explored by algorithm.

Why it matters Tree of partial configurations explored by algorithm. In Backtracking, this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/9

Start at ∅. Try each choice; recurse; undo on failure.

Step 2/9

Pick 1. Partial: [1].

Step 3/9

Pick 2. [1, 2] is a valid permutation. Record.

Step 4/9

Backtrack to [1]. Undo the 2.

Step 5/9

Pick 3. Constraint says no prune ✕.

Step 6/9

Backtrack to ∅.

Step 7/9

Try the other branch. Pick 2.

Step 8/9

Pick 1. [2, 1] is valid. Record.

Step 9/9

Backtrack, try 3. Pruned ✕. Search complete.

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Dynamic programming

Choose this when Choose backtracking when full solution enumeration is needed.

Tradeoff DP is better for overlapping-subproblem optimization tasks.

vs. Greedy

Choose this when Choose backtracking when local choices can invalidate future feasibility.

Tradeoff Greedy is faster when provably correct.

vs. Brute-force loops

Choose this when Choose backtracking for structured recursive search and pruning hooks.

Tradeoff Still exponential in worst case without strong pruning.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Constraint solvers (OR-Tools ecosystem)

Scheduling and assignment engines rely on backtracking + pruning when constraints are complex.

Takeaway Backtracking is practical when exactness matters.

Gaming studios

Puzzle generation/validation often explores candidate states recursively.

Takeaway Search-tree control is crucial in content tooling.

Security tooling

Policy and configuration validation may recursively explore rule combinations.

Takeaway Backtracking helps enumerate valid safe configurations.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Choose unused element, recurse, then undo to explore next branch.

Complexity: Time O(n! * n), Space O(n)

Generate permutations

Language

function permutations(values: number[]): number[][] {
  const result: number[][] = []
  const currentPath: number[] = []
  const usedByIndex = new Array<boolean>(values.length).fill(false)

  function dfs(): void {
    if (currentPath.length === values.length) {
      result.push([...currentPath])
      return
    }
    for (let valueIndex = 0; valueIndex < values.length; valueIndex += 1) {
      if (usedByIndex[valueIndex]) continue
      usedByIndex[valueIndex] = true
      currentPath.push(values[valueIndex])
      dfs()
      currentPath.pop()
      usedByIndex[valueIndex] = false
    }
  }

  dfs()
  return result
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Forgetting to undo state after recursive call.
No pruning leading to timeout on moderate input.
Shared mutable state corruption across branches.
Incorrect base case producing missing or duplicate solutions.
Expensive deep copies on every recursion level.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Backtracking starts with decision tree definition, not code syntax.
Pruning conditions provide most of the performance gains.
Undo every mutation before returning to previous recursion frame.
Sort input first when it helps deduplicate branches cleanly.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

Expressive for search problems with constraints.
Can find all valid solutions, not just one.
Pairs well with pruning heuristics to cut search space.

LeetCode-specific tips (pattern-identification signals)

Identification signal: you must enumerate all valid combinations/permutations/subsets under constraints.
Identification signal: choices are made step-by-step with prune-and-revert behavior when a branch fails.
When prompt asks for "all solutions" rather than one optimum, backtracking is often primary.
For Backtracking questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Subsets	Medium	`O(n*2^n)`
2	Combination Sum	Medium	Exponential
3	Permutations	Medium	`O(n*n!)`
4	Generate Parentheses	Medium	Catalan
5	Palindrome Partitioning	Medium	Exponential
6	Word Search	Medium	`O(mn4^L)`
7	N-Queens	Hard	Exponential
8	Sudoku Solver	Hard	Exponential
9	Word Search II	Hard	Pruned DFS
10	Expression Add Operators	Hard	Exponential