Backtracking

Explore backtracking interview patterns with growing recursion trees for subsets, combinations, permutations and N-Queens. Watch choices get made, undone and pruned.

The pattern

Backtracking: try a choice, explore, undo it

Backtracking builds answers one choice at a time and explores every option, depth first. When a path is finished it records an answer; when a path can't possibly work it gives up on it at once and backs up to try the next option. It's how you list all subsets, combinations, arrangements and placements.

·+1−1+2−2+2−2[1,2][1][2][ ]blue: the path is the current choice list

1A tree of choices

Every backtracking problem is a walk through a tree: each level is one decision, each branch one option. Here: include 1 or not, then include 2 or not. Each leaf is one answer.

append(x)→dfs(…)→pop()then the next choicefor each choice at this level:

2Choose, explore, un-choose

Keep one list for the current path. Append a choice, recurse, then pop it before trying the next choice. The pop is the “back” in backtracking: the list is ready for the sibling branch.

·✗✗✓✗no subtree below ✗an answer

3Prune early

The trees are exponential, so the speed comes from cutting branches as soon as they can't work: a sum past the target, a letter that doesn't match, a queen under attack. Red marks a branch that was cut.

How to spot it

  • “Return all …” subsets, combinations, permutations, partitions: the answer is exponential, so walk the tree.
  • Each item in or out: two branches per level. Pick the next item: one branch per remaining option.
  • Duplicates in the input: sort, then skip equal neighbours at the same level.
  • Placement with rules (queens, paths on a grid): check the rule before recursing.

Reading the pictures

  • The recursion tree grows as the search runs. Each node is one call; its label is the choice that led to it (+x include, −x skip).
  • Blue is the current path, green a recorded answer, red a branch that was cut off. The note beside the current node is its state.
  • For a bigger board with queens, see the N-Queens visualizer.

NeetCode 150 · Backtracking

All 9 problems

Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.

Subsets

Medium

Given distinct numbers, return every possible subset (the power set), including the empty one, in any order.

NeetCode's video solution Try it on LeetCode
Input

nums = [1, 2, 3]

nums

1
i=0
2
i=1
3
i=2

subset so far (the path)

(empty)

subsets found

(empty)

decision tree: +x puts x in, −x leaves it out

·[]

variables

subsets found
0

Press Play or Step to watch the solution run.

Step 0 / 24
900 ms

Brute force vs the pattern

On this input:

Pattern: O(n · 2^n)
15 ops
Brute force
n/a

There's no shortcut: the answer itself has 2^n subsets, so any method takes O(n · 2^n). Counting through the bitmasks 0 … 2^n − 1 is the iterative version of the same tree.

“ops” is an illustrative count of selected algorithm operations, with estimates for sorting. It excludes drawing and frame creation and is not a timing benchmark. The complexity describes the Python solution. On small inputs a brute-force search may find the answer sooner.

How it works: Subsets

Step by step

  • Current call
  • Path from the root: the choices so far
  • A subset recorded

Press Start or Step: the step the animation is on lights up below.

  1. 1

    Start with an empty subset

    res, subset = [], []
  2. 2

    Include nums[i], recurse

    subset.append(nums[i]); dfs(i + 1)
  3. 3

    Undo, then leave nums[i] out

    subset.pop(); dfs(i + 1)
  4. 4

    Past the last number → record

    if i >= len(nums): res.append(subset.copy())
  5. 5

    Every leaf visited

    return res

Make one decision per number, in order: include it or don't. Those decisions form a binary tree; each root-to-leaf path is one subset.

Backtracking walks that tree with a single list: append the number, recurse, then pop it (undo the choice) and recurse again without it. At depth n, copy the list into the results.

Spot it in an interview

  • “All subsets / combinations / arrangements”: the answer is exponential, so walk the decision tree.
  • Each element is a yes/no choice: two branches per level.
time O(n · 2^n)space O(n) besides the output

2^n leaves, and copying each subset costs up to n.

Credits

Learn more from NeetCode

The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.

Problem statements are summarised in our own words; the full versions are on LeetCode.