Backtracking Pattern

Q: What is the difference between Backtracking and DFS?

DFS is a graph-traversal algorithm; it visits each node at most once and does not undo state. Backtracking is a problem-solving strategy that uses DFS over an implicit decision tree and explicitly undoes each choice after exploring it, so the same node (state) can be re-entered through a different path.

Q: How do I know when to prune a branch?

Prune the moment a partial state violates a hard constraint (column attack in N-Queens, sum overshoot in Combination Sum, repeated digit in Sudoku). The earlier the prune, the more branches you cut. A common pattern is to check the constraint before the recursive call rather than after, so you don't pay for descending into an impossible subtree.

Q: Why do Backtracking problems still have exponential complexity even with pruning?

Pruning shrinks the constant factor but the worst-case decision tree still has O(b^d) nodes, where b is the branching factor and d is the recursion depth. For N-Queens that's roughly O(N!), for Subsets it's O(2^N). Pruning makes typical inputs tractable, not the worst case.

Q: When should I use iterative vs recursive backtracking?

Recursion is almost always clearer because the call stack stores the partial state automatically. Convert to an explicit stack only if you hit recursion-depth limits in a language with shallow stacks, or if you need to pause and resume the search (rare in interviews).

The Backtracking pattern explores a decision tree by recursively trying each choice, recording it in the current path, and undoing it before trying the next branch. Pruning illegal partial states early collapses an apparent O(b^d) search into something tractable for small inputs. Typical runtime stays exponential (O(N!) or O(2^N)) with O(N) recursion-depth space.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Complexity

Time: O(N!)
Space: O(N)

When to use Backtracking

The problem asks you to enumerate every valid arrangement (boards, board placements, paths) rather than count or score them.
Each step is a discrete decision (place a queen, pick a letter, color a node) and you need to undo it if it leads nowhere.
You can detect a dead end early using a constraint check (column attack, visited cell, target overshoot) so most branches get pruned.
The input is small (n <= 20) because the worst-case search tree is exponential.
Counting alone is not enough — you must return the actual paths, boards, or words that satisfy the constraint.

Template

function backtrack(state, choices, result) {
  if (isComplete(state)) {
    result.push(serialize(state));
    return;
  }
  for (const choice of choices) {
    if (!isValid(state, choice)) continue;
    apply(state, choice);
    backtrack(state, nextChoices(state, choice), result);
    undo(state, choice);
  }
}

Example LeetCode problems

#	Problem	Difficulty	Frequency
79	Word Search	medium	company favorite
51	N-Queens	hard	classic
52	N-Queens II	hard	less common
37	Sudoku Solver	hard	classic
131	Palindrome Partitioning	medium	frequently asked
93	Restore IP Addresses	medium	company favorite
17	Letter Combinations of a Phone Number	medium	foundational
39	Combination Sum	medium	frequently asked

Common mistakes

Forgetting to undo the choice after the recursive call returns, which corrupts the state for sibling branches.
Pushing the live state object into the result without making a deep copy — every saved result then points to the final mutated state.
Skipping the pruning check, which keeps the worst-case search tree at full size and causes TLE on inputs that should fit easily.
On Word Search, marking a cell as visited but forgetting to unmark it after the recursion returns, which prevents other paths from using that cell.
Using a global mutable list for the current path without snapshotting it before recording a solution.

Frequently asked questions

What is the difference between Backtracking and DFS?

DFS is a graph-traversal algorithm; it visits each node at most once and does not undo state. Backtracking is a problem-solving strategy that uses DFS over an implicit decision tree and explicitly undoes each choice after exploring it, so the same node (state) can be re-entered through a different path.

How do I know when to prune a branch?

Prune the moment a partial state violates a hard constraint (column attack in N-Queens, sum overshoot in Combination Sum, repeated digit in Sudoku). The earlier the prune, the more branches you cut. A common pattern is to check the constraint before the recursive call rather than after, so you don't pay for descending into an impossible subtree.

Why do Backtracking problems still have exponential complexity even with pruning?

Pruning shrinks the constant factor but the worst-case decision tree still has O(b^d) nodes, where b is the branching factor and d is the recursion depth. For N-Queens that's roughly O(N!), for Subsets it's O(2^N). Pruning makes typical inputs tractable, not the worst case.

When should I use iterative vs recursive backtracking?

Recursion is almost always clearer because the call stack stores the partial state automatically. Convert to an explicit stack only if you hit recursion-depth limits in a language with shallow stacks, or if you need to pause and resume the search (rare in interviews).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill the Backtracking pattern under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →