Backtracking Foundations

Backtracking is depth-first search over a space of choices. At each step:

1. make one valid choice,
2. recurse,
3. undo that choice before trying the next one.

The most useful mental model is:

A DFS call represents one partially built answer. Its children are the legal ways to extend that answer.

The “backtracking” part is not recursion by itself. It is restoring shared mutable state so that sibling branches start from exactly the same clean state.

Scope: 15 core problems, not all 17 category labels

NeetCode 250 currently groups 17 problems under Backtracking. These notes focus on the 15 where decision-tree search and state restoration are the main reusable pattern.

Two labelled problems are deliberately outside this guide:

• Partition to K Equal Sum Subsets belongs with 1-D DP / bitmask DP. Backtracking can solve it, but memoized state compression is the durable technique.
• Word Break II belongs with memoized DFS / 1-D DP. The central improvement is caching each suffix’s sentence list.

See Why this guide covers 15 of NeetCode 250’s 17 Backtracking problems for the full 15-problem track.

The DFS contract

Write this sentence before coding:

dfs(state) explores every valid completion of the partial answer described by state.

For example:

• dfs(start) — all choices before start are settled; choose the next item from start....
• dfs(i, remaining) — indices before i are settled; the path still needs remaining.
• dfs(row) — rows before row already contain non-conflicting queens.
• dfs(r, c, wordIndex) — the current path has matched the word through wordIndex - 1.

If you cannot state the meaning of one call precisely, the recursion will feel arbitrary.

The standard shape

function solve(input) {
  const result = [];
  const path = [];
 
  function dfs(state) {
    if (isComplete(state)) {
      result.push([...path]); // copy: path will change later
      return;
    }
 
    for (const choice of choices(state)) {
      if (!isValid(choice, state)) continue;
 
      apply(choice, state);
      path.push(choice);
 
      dfs(nextState(choice, state));
 
      path.pop();
      undo(choice, state);
    }
  }
 
  dfs(initialState(input));
  return result;
}

The exact representation varies, but the order must not:

validate → choose → recurse → undo

For boolean search, return immediately after a successful recursive call—but restore state first if the choice was mutated before the call.

The four questions that create the recurrence

Question	What it decides
What is one choice?	The branches of the tree
What state describes progress?	DFS parameters
When is an answer complete?	Base case
When can a branch never work?	Pruning

Then add two implementation questions:

Question	What it protects
What is shared and mutable?	What must be undone
Could different paths produce the same answer?	Whether to sort / skip duplicates

Output, existence, and counting

The decision tree can be the same while the return value changes.

Goal	At a complete valid path	Recursive behavior
List all answers	add a copy to result	explore every branch
Find one answer	return true	short-circuit on success
Count answers	add 1	sum counts or increment a counter

N-Queens and N-Queens II are the clearest pair: same placement tree; one saves boards, the other counts leaves.

State types you will see

State	Typical problems	Why it exists
start index	subsets, combinations	prevents reordered duplicates
remaining target	Combination Sum	makes the goal and pruning explicit
used flags / counts	permutations	knows which value can be next
path	all enumeration problems	builds the candidate answer
visited cells	Word Search	prevents reuse only within this path
constraint sets	N-Queens	checks placement legality in O(1)
bucket sums	Matchsticks to Square	checks whether an item fits

Duplicate rule: tree level, not global

When the input has duplicate values and answers must be unique:

1. Sort the input so equal values are adjacent.
2. At a single DFS depth, only let the first occurrence begin a branch.

for (let i = start; i < nums.length; i++) {
  if (i > start && nums[i] === nums[i - 1]) continue;
  // choose nums[i]
}

i > start is essential. It says “skip this value only if an identical value already made a choice at this depth.” It does not ban using equal values at deeper levels when the problem permits them.

Pruning is a proof of impossibility

Good pruning is not a guess. It is a fact that the current partial path cannot become valid.

Common proofs:

• remaining < 0: a positive-number target cannot recover.
• candidate > remaining after sorting: all later candidates also fail.
• a queen conflicts with a used column or diagonal: no completion can repair it.
• an item would overflow its bucket: later choices cannot undo that overflow.
• two empty or equal-sum buckets are interchangeable: trying both repeats the same state.

Sorting descending is useful for bucket placement: big items expose impossible branches early. Sorting ascending is useful for target sums: it lets candidate > remaining stop the rest of a loop.

Backtracking vs. memoization

Backtracking explores choices. Memoization remembers that the same full state has already failed or has a known answer.

Use plain backtracking first when the constraints are small and pruning is strong. Add memoization when different decision orders reach the same state repeatedly—for example, a bitmask of used values plus a partial bucket sum.

Do not memoize a state that is missing relevant information. Two calls are only interchangeable if every future legal choice is the same.

Complexity language

Enumeration is often exponential because the output itself is exponential.

Family	Leaves / output bound
Subsets of n items	2^n
Choose k from n	C(n, k)
Permutations	n!
Phone keypad	at most 4^n
Word Search for a word of length L	at most rows * cols * 4 * 3^(L - 1)

For a function that returns lists, include the cost to copy each answer: subsets are O(n * 2^n), and permutations are O(n * n!). State the auxiliary space separately from returned output.

Debugging checklist

When an answer is missing, duplicated, or corrupted, check these in order:

1. Is the base case reached before exploring past the end?
2. Did every successful result save a copy of path?
3. Is every push, mark, or add paired with a pop, restore, or delete?
4. Does the DFS parameter move forward correctly?
5. Are duplicates skipped only at the same depth?
6. Is pruning definitely safe?

Core invariant

At the moment a DFS call returns, every shared mutable structure must be exactly as it was when that call began.

That invariant makes recursive branches independent. Protect it, and most backtracking code becomes straightforward.

Next: 01 - Subsets and Duplicates