How to Design a Backtracking Solution

Backtracking tries every possibility, one choice at a time, and steps back when a path can't succeed. You use it when the problem asks for all arrangements, or for any one arrangement that satisfies constraints, and there are many choices along the way. The skill isn't the recursion itself. It's translating the English problem into a decision tree before you write any code.

The six questions#

Answer these on paper first. Don't start coding until each one has a clear answer.

What is the ask? All solutions, one solution, a count, or the best value?
What calculations do you need? Split the task into small steps and note them down.
Goal (base case, success): when do you take a snapshot of your work? For example, the path has k items, or the remaining target is 0.
Hard stop (base case, failure): when is a path purely a waste of time? For example, the sum went over the target, or you stepped off the grid.
Choices (the loop): from your current spot, where can you go?
State (arguments or shared state): what does the child need from the parent? Pass it as arguments, or keep it shared and make the change, recurse, then undo it.

Then prune: remove any branch that can't lead to a valid answer.

Choices and state, by example#

The choice loop sets the branching factor, and the state is whatever the next call needs.

Problem	Choices at each step	Typical state
Subsets	include this number, or skip it (2)	`index`, `path`
Grid search	up, down, left, right (4)	`(r, c)`, `visited`
Sudoku	digits 1 to 9 (9)	cell position, row/col/box sets
Permutations	any unused number (N, then N−1, …)	`path`, `used`
Target sums	any candidate from `start` on	`start`, remaining target

Template#

Once you have the six answers, they slot into one skeleton: choose, explore, un-choose. Here it generates subsets. Every backtracking note in this topic uses this same shape with different answers to the six questions.

result = empty list
path = empty list
track(start):
    record a copy of path in result    # goal: every node is a subset
    for i from start to n - 1:         # choices: any later element
        append items[i] to path        # choose
        track(i + 1)                   # explore with the updated state
        pop the last item from path    # un-choose: restore for the sibling
track(0)
return result

Record a copy of the path, not the path itself. The list keeps changing, so storing the object would leave every result pointing at the same (finally empty) list. In Python the copy is path[:].

Estimating the cost#

Before you code the tree, check that it's small enough to search. Time is roughly branches ^ depth, times the work at each leaf (often $O(N)$ to copy the path). Branches is the size of your for loop and depth is the number of steps to the base case.

Archetype	Branching	Depth	Time	Trigger words
A. Binary choice	2 (take or skip)	N	$O(N \cdot 2^N)$ with copying	subsets, combinations, partition
B. Permutation	N, N−1, …	N	$O(N \cdot N!)$	permutations, arrangements, ordering, N-Queens
C. Fixed options	k (never shrinks)	steps	$O(k^{\text{steps}})$	grid paths, Sudoku ( $9^M$ for M empty cells), phone letters ( $4^N$ )

Two refinements come up often:

Word search has 4 directions at the first letter but only 3 afterward (you can't step back onto the cell you came from), so it's $O(R \cdot C \cdot 3^L)$ for a word of length L.
Partition into k buckets is $O(k^N)$ naively: each of N items picks one of k buckets.

Let the constraints tell you#

If you can't work out the math, look at the input size. The constraints usually hint at the complexity the problem expects.

Constraint	Likely complexity	Approach
N ≤ 12	$O(N!)$	permutations, N-Queens
N ≤ 20 to 22	$O(2^N)$	subsets, combinations, partitions, bitmasks
N ≤ 100	polynomial	DP; backtracking will time out
N ≤ 500	$O(N^2)$ to $O(N^3)$	DP, 2D grids
small grid, short word	$O(R \cdot C \cdot 3^L)$	grid DFS (Word Search)

What pruning buys#

Pruning doesn't change the worst-case complexity, but it cuts the average case by a lot. A used array, sorting so you can break early, and bailing out on impossible states all trim the tree. The theoretical height stays the same; you explore far fewer branches.

Construct, don't filter#

The cheapest pruning is never generating invalid states at all. Before you write a "check if valid" step at the leaf, ask whether the choice loop could offer only valid options. Two common moves:

Fill half, mirror the rest. When the answer is symmetric, choose only the first half and derive the second. The tree depth halves, so the cost drops from $k^n$ to about $k^{n/2}$ , and every leaf is valid.
Stop when too few options remain. If the path cannot reach the required size with the items left, return early.

Strobogrammatic Number II is the classic example of the first move (see its hint). The "not enough numbers left" check in Combinations is the second.

Cheat sheet#

Most of the core patterns differ in only two places: where the loop starts and which index the recursive call gets. This table puts them side by side.

Pattern	Key strategy	Loop and recursive call
Subsets	decide for each index: take or skip	`range(start, n)`, recurse with `i + 1`
Combinations (size k)	pick k items	`range(start, n)`, stop at size k
Permutations	try every unused number	`range(0, n)` plus a `used` check
Sum with reuse	a number can be used again	recurse with `i`
Sum without reuse	each number at most once	recurse with `i + 1`
Duplicates in input	skip identical siblings	sort, then `if i > start and nums[i] == nums[i - 1]: continue`

When backtracking meets DP or BFS#

Plain backtracking isn't always enough. Some problems start as backtracking and need a second tool on top.

Repeated states: if the same (index, remaining) or (index, used-mask) comes up again and again, memoize it. That's the bridge into Dynamic Programming.
Fewest changes: when the question asks for the minimum number of edits, explore level by level with BFS. The first level that yields a valid answer uses the fewest changes.

Pitfalls#

The two most common weak spots are state management and complexity analysis.

Forgetting to undo. Every change made before the recursive call (path, counters, visited marks, running score) must be reversed after it.
Storing the live path. Append a copy, path[:].
Wrong recursive index. i allows reuse, i + 1 doesn't, and start + 1 (instead of i + 1) produces duplicates.
Guessing complexity. Draw the tree: count the branches per node and the depth.
Coding before the six answers are clear. Most bugs come from an unclear goal or hard stop.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Subsets, Permutations and Combination Sum.

Hints#

Open a hint only after you have tried the problem for a while. For each one, answer the six questions first.

Hint: Subsets

Every node of the tree is a valid subset, so record a copy on entry. The choices are the elements from start on, and the child gets i + 1.

Hint: Permutations

Order matters, so the loop always starts at 0. Keep a used array and skip any element already in the path. The goal is a path of length n.

Hint: Combination Sum

A candidate can be used again, so recurse with i, not i + 1. The hard stop is a remaining target below zero; the goal is exactly zero.

Hint: Word Search

Start a DFS from every cell that matches the first letter. Mark the cell as visited before you recurse and unmark it after. After the first step only 3 directions are new, so the cost is $O(R \cdot C \cdot 3^L)$ .

Hint: N-Queens

Place one queen per row, so the depth is n and rows never clash. Keep sets for used columns and both diagonals (r - c and r + c) for an $O(1)$ check.

Hint: Letter Combinations of a Phone Number

This is the fixed-options archetype. The depth is the number of digits, and the choices are the 3 or 4 letters of the current digit.

Hint: Strobogrammatic Number II

Construct, don't filter. Fill only the first half from {0, 1, 6, 8, 9}, and each time you place a digit at i, place its rotated partner (6 and 9 swap, the others map to themselves) at n - 1 - i. The outer digit can't be 0, and for odd n the center can only be 0, 1 or 8. The base case is the middle index n // 2, not n.

Hint: Word Break II

Plain DFS over prefixes repeats the same suffix many times. Memoize the list of segmentations for each start index, and build each answer from the memo of the rest.

Hint: Remove Invalid Parentheses

You need the fewest removals, so use BFS: each level removes one more character. Stop at the first level that yields any valid string, and collect every valid string on that level. Use a set to skip strings you have already seen.

Hint: Generate Parentheses

The choice at each step is ( or ). Add ( while opens are left, and add ) only while closes used stay below opens used. Record the string when it reaches length 2n.

Hint: Binary Watch

There are only 10 LEDs, so either choose which k are on with backtracking, or loop over every hour and minute and keep the times whose bit counts add up to k. Both teach the same choose-and-check shape.

Key takeaways#

Answer the six questions (ask, calculations, goal, hard stop, choices, state) before coding.
Choose, explore, un-choose; snapshot a copy of the path (path[:]).
Time is about branches ^ depth; the input size usually tells you which bucket you're in.
Pruning cuts the average case, not the worst case.
Construct only valid states instead of generating everything and filtering.

Core idea#

Backtracking tries every possibility one choice at a time and steps back when a path cannot succeed. Turn the problem into a decision tree before you write code.

Key points#

Answer six questions first: the ask, the calculations, the goal, the hard stop, the choices and the state.
Goal: when to snapshot the path. Hard stop: when a path is a waste of time.
Choices are the for loop. State is what the child needs from the parent.
Shared state follows one rule: make the change, recurse, then undo it.
Time is about branches ^ depth, times the leaf work (often $O(N)$ to copy the path).
Pruning cuts the average case, not the worst case.
Construct only valid states instead of generating everything and filtering. Strobogrammatic Number II fills only the first half and mirrors each digit.

Cost by archetype#

Archetype	Branching	Time	Trigger words
Binary choice	2	$O(N \cdot 2^N)$	subsets, combinations, partition
Permutation	N, N−1, …	$O(N \cdot N!)$	arrangements, ordering, N-Queens
Fixed options	k	$O(k^{\text{steps}})$	grid paths, Sudoku, phone letters

Constraints tell you the bucket: N ≤ 12 means $O(N!)$ , N ≤ 20 to 22 means $O(2^N)$ , N ≤ 100 means DP. Word search is $O(R \cdot C \cdot 3^L)$ .

Loop and recursive call#

Pattern	Loop	Recurse with
Subsets, combinations	`range(start, n)`	`i + 1`
Permutations	`range(0, n)` plus `used`	no index
Sum with reuse	`range(start, n)`	`i`
Duplicates in input	sort, skip `nums[i] == nums[i - 1]` when `i > start`	`i + 1`

Template#

track(start):
    record a copy of path            # goal: snapshot a copy
    for i from start to n - 1:
        append items[i] to path      # choose
        track(i + 1)                 # explore
        pop from path                # un-choose
track(0)

Pitfalls#

Forgetting to undo a change after the recursive call.
Appending path instead of path[:]. Every result then points to one list.
Recursing with start + 1 instead of i + 1. That produces duplicates.
Repeated states such as (index, remaining). Memoize them; that is the bridge to DP.

Say it in an interview#

"Choose, explore, un-choose. The base case snapshots a copy of the path."
"Time is branches to the power of depth, and the constraints confirm it."