Backtracking

Backtracking is brute force with a brain. You build a candidate solution one decision at a time, recurse to explore the consequences, and then undo the decision before trying the next option. That undo step — restoring the state to exactly what it was — is what lets one recursive function explore every branch of a giant decision tree without making fresh copies at every turn.

We will enumerate every subset of nums = [1, 2, 3]. For each index i we make one binary decision: include nums[i] in the current subset, or skip it. Walking that decision tree to its leaves gives all 8 subsets.

Intuition

Think of a row of light switches, one per number. Every subset is just one setting of all the switches — on means "in the subset," off means "out." To list every possible setting, you flip the first switch on, then recursively try every setting of the remaining switches; then flip it off and try them all again.

That is exactly the include/exclude DFS. The shared path list is the set of switches currently flipped on. When recursion reaches the end of the array, path holds one complete subset, so we record a snapshot of it. The crucial detail is the un-choose: after exploring the "include" branch we pop the number back off, so the "exclude" branch starts from the same clean state instead of inheriting leftovers.

Walk through it

Step through the animation on the right. The pointer i marks the index we are deciding about, path shows the partial subset, and results grows as leaves are reached.

Starting at i = 0, we include 1 — its cell lights up and path becomes [1]. We recurse and include 2, then include 3; now i is past the end, so we record [1, 2, 3]. We then backtrack: pop 3, explore the branch that skips it, and record [1, 2]. Backtracking keeps peeling decisions off — pop 2, skip it, dive back in to record [1, 3] and [1]. Once the whole "include 1" subtree is exhausted, we pop 1 itself and explore everything that skips 1, producing [2, 3], [2], [3], and finally the empty subset []. Eight leaves, eight subsets.

The code, line by line

def subsets(nums):
    results = []
 
    def backtrack(i, path):
        if i == len(nums):
            results.append(path[:])
            return
        path.append(nums[i])   # choose
        backtrack(i + 1, path) # explore
        path.pop()             # un-choose
        backtrack(i + 1, path) # explore skip
 
    backtrack(0, [])
    return results

• The base case (line 5) fires when i runs past the array: path is a finished subset, so we append a copy with path[:]. Appending path itself would store a reference that later mutations corrupt.
• Line 8 is choose: push nums[i] onto the shared path.
• Line 9 explores that choice — recurse on the next index with nums[i] included.
• Line 10 is un-choose: pop nums[i] back off so the state is restored. This is the heart of backtracking.
• Line 11 explores the skip branch: recurse on the next index with nums[i] left out.
• backtrack(0, []) starts the whole thing with an empty path; results collects every leaf.

Complexity

There are 2^n subsets because every element is independently in or out, and copying each finished path costs O(n) — hence O(n * 2^n) total. The recursion stack only ever goes n deep and path holds at most n values, so the working space (not counting the output list itself) is O(n).

When to use / pitfalls

Practice