Coding

Backtracking

Build candidates incrementally, undo on dead ends.

Coding pattern

Overview

Backtracking builds candidate solutions incrementally and abandons a path the moment it can't lead to a valid answer. It's the go-to for permutations, combinations, and constraint puzzles where you must explore choices but prune aggressively.

How it works

Coding pattern

ClientServiceEdgeData

Step by step, with examples

1
Pick option
- Try a candidate choice.
2
Recurse
- Go deeper with that choice.
3
Constraint
- Abandon invalid paths early.
4
Backtrack
- Undo and try the next option.
- Example: N-Queens, permutations

When to reach for it

Permutations / combinations
Sudoku / N-Queens
Constraint satisfaction

Example problem

Generate all subsets of a set.

Approach

Choose / explore / un-choose
Record the path at each node

Solution

function subsets(nums) {
  const res = [], path = [];
  const dfs = (i) => {
    if (i === nums.length) { res.push([...path]); return; }
    dfs(i + 1);                 // skip
    path.push(nums[i]); dfs(i + 1); path.pop(); // take
  };
  dfs(0);
  return res;
}

Complexity

Time O(2^n), Space O(n) recursion.

Common pitfalls

Forgetting to undo state
Pushing references not copies

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions