Data structures & algorithms · Backtracking

Choose, explore, un-choose

Q: What is the space complexity, given there are 2ⁿ answers?

O(n) , not O(2ⁿ) , if you do not count the output. Only one root-to-leaf path is alive at any instant: n stack frames and one shared list of at most n items. The 2ⁿ leaves are visited one at a time and never held together, unless you are collecting them, and then the collection is the space cost, not the search.

Three lines generate every subset and every permutation. This page traces all subsets of 1 2 3 and makes the third line — the one everybody leaves out — impossible to miss.

Grow the search tree, then un-grow it →

1 · ChoosePut one option into the working answer. cur.push(3)

→

2 · ExploreRecurse, and let the deeper calls finish every answer that starts this way.

→

3 · Un-choosecur.pop() — the line people leave out.

01 The idea

Recursion, plus an undo

Some problems ask for every valid answer, not the best one. Every subset of a list. Every ordering of four names. Every way to place eight queens so that none attacks another. There is no formula to plug into. You have to build candidates one decision at a time.

Backtracking is how you do that without losing track. You keep one working answer — a single list — and you make one decision at a time. When you have finished exploring everything that follows from a decision, you take that decision back and try the next one. All those partial answers form a tree, and your recursion is a depth-first walk of it. You never store the tree; it exists only as the chain of calls on the stack.

Choose one option. Explore everything that follows from it. Then un-choose it, so the next option starts from the exact state you did. Three lines, in that order — and the third one is the one people leave out.

State-space treeEach node is a partial answer, each edge is one decision, each leaf is a finished candidate. Three items with take-or-skip on each gives 8 leaves and 15 nodes.

Choose · explore · un-chooseThe template. Add the decision to your working answer, recurse, then remove it again. Add, recurse, remove — in that order, every level.

PruningReturning from a node before you explore its children, because the partial answer already breaks a rule. One return deletes a whole subtree, not one node.

02 Hand trace

Every subset of 1 2 3, one action at a time

Take the array 1 2 3 and ask for every subset. At each level you face the same question about one item: take it, or skip it. Two choices, three times over, so 2 × 2 × 2 = 8 subsets. Below is the left half of that tree — every branch that takes the 1 — written out action by action. The boxes are cur, the one working list every call shares. A rose note means the search is still mid-flight; a green note means a subset has just been written down.

choose 11··pushed 1 · go down to level 1

choose 212·pushed 2 · go down to level 2

choose 3123pushed 3 · go down to level 3

record123level 3 is past the last item — write down {1, 2, 3}

un-choose 312·popped 3 · cur is what the choose-2 row left it

record12·skip 3, reach level 3 again — write down {1, 2}

un-choose 21··popped 2 · back at level 1, now skipping the 2

choose 313·this branch skipped 2, so 3 lands next to the 1

record13·write down {1, 3}

un-choose 31··popped 3 · cur holds the 1 only

record1··skip 3 as well — write down {1}

un-choose 1···popped 1 · cur is empty again, ready for the other half

Read the labels down the left, not the boxes. Four chooses and four un-chooses, and they interleave — the first three rows are chooses in a row, but the pops that answer them come back one at a time, threaded between the branches. It is never four chooses followed by four un-chooses at the end. Each un-choose sits between the branch that has just finished and the branch about to start, and its only job is to hand that next branch the same cur the previous one received.

Two details are worth pausing on. A skip branch — the ones named in the green notes — has no matching un-choose, because it never pushed anything, so there is nothing to pop. And twelve rows in, cur is empty again after finding {1, 2, 3}, {1, 2}, {1, 3} and {1} — the four subsets that contain the 1. The other four, {2, 3}, {2}, {3} and the empty set, come from the half of the tree that skipped the 1 at level 0. The final un-choose is what makes that half start from an empty list instead of inheriting a decision.

03 Code

The template, and the bug you cannot see

The trace is the whole algorithm, so write it down. n is the number of items, a is the array, i is the level, and cur is the working list that every call shares. This shape is called pick / not-pick: line 5 explores everything that includes a[i], line 7 explores everything that does not, and the base case at line 2 fires when there is nothing left to decide.

The version on the left is what students hand in. It has the choose and it has both explores. What it does not have is the pop.

Broken · no un-choose

function subsets(i, cur):    if i == n:        record(cur); return    cur.push(a[i])        # choose    subsets(i + 1, cur)   # explore     subsets(i + 1, cur)   # cur still holds a[i]

Correct · choose, explore, un-choose

function subsets(i, cur):    if i == n:        record(cur); return    cur.push(a[i])        # 1 choose    subsets(i + 1, cur)   # 2 explore    cur.pop()             # 3 un-choose    subsets(i + 1, cur)   # explore without a[i]

The pop is not tidying up — it is the next branch's setup. Line 5 finishes everything that starts with a[i]. Line 7 starts everything that does not. Between the two, cur has to lose a[i], or line 7 inherits a decision it never made. The un-choose belongs to the sibling branch, not to the branch that just ended.

The broken version's first answer is correct, which is exactly why it survives. Run the left version on 1 2 3 and the first thing it records is {1, 2, 3} — right. The second is {1, 2, 3} again, then {1, 2, 3, 3} twice, then {1, 2, 3, 3, 2, 3}. Eight records still come out, so even the count looks plausible, and the empty set never appears at all. Check the last line of your output, not the first.

One list, shared by every frame. Every call pushes onto the same cur, so the working space is one list of at most n items — O(n). The alternative is to hand each call its own copy; then there is nothing to un-choose, because the copy was the undo. You pay an O(n) copy at every node instead of an O(1) push and pop — that is all 2ⁿ⁺¹ − 1 of them, 15 for three items — and because every live frame now holds its own list, the working space becomes O(n²).

Pruning. Add one check at the top of the function and you stop exploring a node whose partial answer already breaks a rule. It is only safe when the breach cannot be repaired further down: a sudoku grid that already has two 5s in one row still has two 5s in it however you fill the rest, so returning there loses nothing valid. Ask that question before you add any cut — a test that a deeper choice could still undo will silently delete real answers. On three items pruning saves almost nothing. On twenty it is the whole game: kill a node at level 3 and one return has deleted 2¹⁷ = 131,072 leaves.

05 Cheat sheet

The four problems you will be asked

Problem	Answers	Cost to produce them	Stack depth
Subsets of n items · pick / not-pick	2ⁿ	`O(n · 2ⁿ)`	`O(n)`
Permutations of n items · by swapping	n!	`O(n · n!)`	`O(n)`
Combination sum · candidates reusable, target t, smallest candidate m	input-dependent	`O(n^(t/m))`	`O(t/m)`
N-Queens on an n × n board · one queen per row	92 when n = 8	`O(nⁿ)` blind, `O(n!)` on the column rule alone	`O(n)`

The output is the costWhen the answer is 2ⁿ subsets, nothing beats 2ⁿ. Backtracking's win is never the enumeration — it is being able to abandon a subtree that cannot contain an answer.

Depth is memory, width is timeOne frame per level plus one shared working list, so O(n) space even with 2ⁿ leaves. The leaf count is your time bill, not your memory bill.

Chooses must equal un-choosesEvery push is matched by exactly one pop. All subsets of 1 2 3: 7 pushes, 7 pops, 8 subsets, 15 nodes. If the first two numbers differ, the bug is in your template.

06 Where & why

Brute force, with a conscience

Backtracking still walks an exponential tree, and no amount of clever coding changes that. What it buys you is two things: O(n) memory while it walks, and the right to delete an entire subtree the moment the partial answer is already illegal.

Reach for it when…

You need every valid answer, listedAll subsets, all permutations, all safe queen placements, all paths through a maze. When the question says "return all", this is the shape it wants.

A half-built answer can be judgedYou can tell that a queen is already attacked, or a running sum is already past the target, before the answer is finished. That test is what makes the real tree smaller than the formula.

n is smallUnder about 20 for subsets, since 2²⁰ is 1,048,576, and about 10 for permutations, since 10! is 3,628,800. Past that the tree does not finish, pruning or not.

The rules are easier to check than to countTesting whether a sudoku grid is legal takes three lines. A closed form for how many legal grids exist is a research paper.

Use something else when…

Situation	Better choice	Why
You need the count, not the arrangements	A DP table, or a closed form	Counting the subsets that hit a target sum is `O(n · t)` with a table. Listing them is `O(2ⁿ)`.
Many different paths reach the same state	Memoisation, or bottom-up DP	Backtracking re-solves that state once per path. Caching on the state collapses the tree into a table.
You want one good answer fast, not all of them	Greedy, or branch and bound	Keep the best answer so far and cut any branch whose best possible finish cannot beat it.
The tree resists pruning and n is large — a route through 100 cities	Heuristics, or an ILP solver	99! candidate routes. Nothing enumerates that, so you take a good answer with a proven bound instead.

You will rarely write a raw backtracker at work, and you will use one every day: sudoku solvers, regex engines, SAT and constraint solvers, test-case generators, and every "show me all valid combinations" screen. Interviews ask for it because the un-choose line is the shortest test there is of whether you know what a call owns and what it shares.

07 Interview questions

Say these out loud

Question four is the one that separates people who have read about backtracking from people who have debugged it.

What is backtracking?

A depth-first search over partial answers. You build one candidate a decision at a time, and when a decision is finished with or turns out to be illegal, you undo it and try the next option. The three steps are choose, explore, un-choose, and it is the undo that makes it backtracking rather than plain recursion.

Give me the template.

choose — put the decision into the working answer. explore — recurse on what is left. un-choose — remove the decision you just made. A base case at the top records the answer when there is nothing left to decide. Subsets, permutations, combination sum, sudoku and N-Queens are all that skeleton with a different legality test.

Why do you need the un-choose at all?

Because every call shares one working list. The pop returns that list to the state the current level received it in, so the next sibling branch starts from the same place this one did. Without it the second branch inherits a decision the first branch made, and every answer after the first one is wrong.

What exactly happens if you forget the pop when generating subsets?

The working list keeps growing instead of resetting. On 1 2 3 you get {1,2,3}, then {1,2,3} again, then {1,2,3,3} twice, and the empty set never appears. The number of records is still 8, so it does not crash and the count still looks right — you have to read the last line of the output, not the first.

If you pass a fresh copy of the list into each call, do you still need the un-choose?

No, because the copy is the undo — the callee's pushes never touch the caller's list. You pay for it: an O(n) copy at every node in the tree instead of an O(1) push and pop, and space goes from one shared list to one list per live frame. Interviewers accept the copy version and then ask you for the in-place one.

How big is the tree?

For subsets it is one binary decision per item, so 2ⁿ leaves and 2ⁿ⁺¹ − 1 nodes — 8 leaves and 15 nodes for three items. For permutations by swapping there are n choices for the first position and n − 1 for the next, giving n! leaves. Producing the answers costs an extra factor of n on top, because each finished candidate has to be copied out.

What is the space complexity, given there are 2ⁿ answers?

O(n), not O(2ⁿ), if you do not count the output. Only one root-to-leaf path is alive at any instant: n stack frames and one shared list of at most n items. The 2ⁿ leaves are visited one at a time and never held together, unless you are collecting them, and then the collection is the space cost, not the search.

What is pruning, and how much does it actually save?

One return at the top of the function when the partial answer already breaks a rule, before any child is explored. It deletes a subtree, not a node: cut a node at level 3 of a 20-item pick / not-pick tree and 2¹⁷ = 131,072 leaves go with it. The worst case is unchanged — a pruned backtracker is still exponential — but on real input it is the difference between finishing and not.

Backtracking or dynamic programming?

Backtracking when you need the arrangements themselves, DP when you need a count or an optimum. DP works by collapsing every path that reaches the same state into one table cell, and that collapse is exactly why it can no longer tell you which choices got there. So if the recursion has overlapping subproblems and you only want a number, memoise it and stop listing.

Is backtracking just DFS?

Hard

The console insists on distinct numbers. Drop that rule: for 1 2 2, pick / not-pick still records 8 answers, but only 6 of them are different. Return each distinct subset exactly once, without collecting them all and de-duplicating at the end.

Follow-up

Sorting first is necessary but nowhere near sufficient, and the fix is not in the take branch — it is the skip branch that has to refuse to run twice for the same value. Work out which of the two branches produces the duplicate pair before you write a line.

Show the hint

Take one repeated value and hand-trace the two branches that both end up recording {2}. They differ only in which copy of the 2 they used — so make the skip branch skip every remaining copy at once, not just one.