Algorithm • hard

Backtracking Complete Guide

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

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

Solve ANY Backtracking Problem on Leetcode

Channel: Bitflip

Full video link:

https://www.youtube.com/watch?v=p9m2LHBW81M

Backtracking Visualizer

Build candidate solutions, detect invalid branches early, then undo and try alternatives.

Backtracking VisualizerStep 1 / 3

Start with empty partial solution.

Problem

Permutations of [1,2,3]

Current Path

[]

Remaining Choices

[1,2,3]

Action

Choose 1 and recurse.

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

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.

Putting It All Together

This walkthrough connects the core concepts of Backtracking into one end-to-end execution flow.

Step 1

Decision tree

Implicit tree of candidate choices.

Before

Need permutations of

123

Path=[], used={}

→

After

Path grows depth-first
Search tree explored incrementally

Transition

Choose one unused candidate

→Append to path and recurse

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

Step 2

State

Current partial solution.

Before

Path=

Remaining candidate: 3

→

After

Record solution

123

Return to previous frame

Transition

Choose 3

→Reach complete solution length

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

Step 3

Choice set

Available next options from current state.

Before

Back at path=

123

Need alternate branch

→

After

Path=

Ready for next candidate

Transition

Undo last choice (pop 3)

→Mark 3 unused again

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

Step 4

Constraint check

Pruning condition to stop invalid branches early.

Before

Constraint check available
Some branches invalid early

→

After

Less search work
Correct solutions preserved

Transition

Prune invalid branch before deeper recursion

→Skip impossible subtree

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

How It Compares

vs Dynamic programming

When to choose this: Choose backtracking when full solution enumeration is needed.

Tradeoff: DP is better for overlapping-subproblem optimization tasks.

vs Greedy

When to choose this: Choose backtracking when local choices can invalidate future feasibility.

Tradeoff: Greedy is faster when provably correct.

vs Brute-force loops

When to choose this: Choose backtracking for structured recursive search and pruning hooks.

Tradeoff: Still exponential in worst case without strong pruning.

Real-World Stories and Company Examples

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.

Implementation Guide

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

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

Language

Generate permutations

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
}

Common Problems and Failure Modes

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.

Tips and Tricks

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.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

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 (including 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.

LeetCode Progression (Easy to Hard)

Back to DSA Guide Catalog

#	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