Backtracking

How Backtracking works

Before you start

Recursion
Backtracking is recursion that undoes a choice. That lesson covers the call stack.
Open lesson

Why it matters

Feature-flag matrices, test-case generators, and combinatorial searches often need every selection from a set. The output is already exponential, so extra copying or duplicate generation quickly makes the unavoidable work much worse. Every one of the 2ⁿ subsets must appear exactly once while temporary memory stays proportional to n.

Example

Subsets

Return every subset of nums (the power set). Sort each subset, then sort the list of subsets by length then lexicographically.

Input: nums = [1, 2, 3]
Output: [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

Mental model

The idea

Keep one example in view

Subsets

nums = [1, 2, 3]→[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

Keep this exact scenario and its constraint in view while you build the model.

For [1, 2, 3], rebuilding all eight subsets independently repeats prefixes such as [1, 2]. Reuse one path through include-or-skip decisions: append before a choice, pop after it, and copy only the eight finished subsets.

For [1, 2, 3], choose(0) first appends 1, choose(1) appends 2, and choose(2) appends 3. At i = 3, record [1, 2, 3]. Pop 3 and take its skip branch to record [1, 2].

Continue by popping 2, exploring [1, 3] and [1], then popping 1 and producing [2, 3], [2], [3], and []. path is copied only at a leaf because later pops mutate the working list; every internal prefix is reused by both branches.

Visual anchor

Subsets

path∅

Each leaf of the decision tree is one subset. path was one list the whole time, grown on the way down and shrunk on the way back.

Run the same example

Walkthrough

1.choose(i): if i equals len(nums), record a copy of path.
2.Otherwise append nums[i], call choose(i + 1), then pop it.
3.Call choose(i + 1) again, this time without nums[i].

Python

Subsets

Input:: nums = [1, 2, 3]
Output:: [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

1def subsets(nums):
2 result, path = [], []
3 def choose(i):
4 if i == len(nums):
5 result.append(path[:])
6 return
7 path.append(nums[i])
8 choose(i + 1)
9 path.pop()
10 choose(i + 1)
11 choose(0)
12 return result

path∅

Calling

Each level decides one number: the left branch includes it, the right branch skips it.

1 / 10

Complexity

TimeO(n · 2ⁿ)

SpaceO(n)

There are 2ⁿ subsets, and copying each one costs up to n, so time is O(n · 2ⁿ). No approach can do better, because that is the size of the output. Besides the output, path and the call stack hold at most n items: O(n) space.

Where this breaks

Include-or-skip lists every subset. It does not stop at the first subset that sums to a target, and repeated numbers produce duplicate subsets.

Your turn

Subsets

Same problem, your code.

Solve Subsets

Then branch out

Same technique, different problems. Try them without the walkthrough.