Subsets: Backtracking Decision Tree

Given an array of unique integers, return all possible subsets (the power set). The solution must not contain duplicate subsets.

This is LeetCode 78: Subsets, and it is one of the cleanest backtracking problems out there. While Word Search applies the choose-explore-unchoose pattern to a grid, Subsets strips the pattern down to its simplest form: for each element, include it or skip it. That binary decision at every level builds a decision tree whose leaves are all 2^n subsets.

Why this problem matters

Subsets is the "hello world" of backtracking. Almost every backtracking problem follows the same shape: make a choice, recurse, undo the choice. In Subsets, the choice is trivially simple (include or skip one element), so you can focus entirely on the recursive structure without getting distracted by boundary checks, constraint validation, or grid neighbors.

Once you can generate all subsets from scratch, you have the mental model for generating permutations, combinations, combination sums, and partition problems. The only things that change between those problems are the branching rules and the base case. The skeleton is always the same.

Understanding how backtracking subsets works also makes you comfortable with the idea that a backtracking algorithm explores a tree of choices. That mental picture is critical for analyzing time complexity and for recognizing when a problem is asking you to enumerate all possibilities.

The key insight

Think of each element as a yes-or-no question. "Do I include nums[i] in the current subset?" If there are n elements, there are n binary questions, which means 2^n total combinations. Every unique path from the root to a leaf of the decision tree produces exactly one subset.

The algorithm works like this:

1. Start with an empty subset and index 0.
2. At index i, add the current subset to the result (every node in the tree is a valid subset).
3. For each remaining element from i to n-1, choose it (append to current), explore (recurse with the next index), and unchoose it (pop it back off).
4. When the index reaches n, you have no more elements to consider. The recursion bottoms out naturally.

The backtracking solution

def subsets(nums: list[int]) -> list[list[int]]:
    result = []

    def backtrack(start, current):
        # Every node in the tree is a valid subset
        result.append(current[:])

        for i in range(start, len(nums)):
            current.append(nums[i])    # choose
            backtrack(i + 1, current)   # explore
            current.pop()               # unchoose

    backtrack(0, [])
    return result

Let's break this down.

The outer function initializes result as an empty list, then kicks off backtrack(0, []). The first argument is the starting index (so we only consider elements we have not already decided on), and the second is the subset we are building.

Inside backtrack, the very first thing we do is record current[:] (a copy of the current subset) into result. This is different from problems like Word Search where you only record at leaf nodes. In Subsets, every partial subset is valid, so we record at every node.

The for loop iterates over all elements from start to the end of the array. For each element nums[i], we append it (choose), recurse with i + 1 (explore elements after it), and then pop it off (unchoose). The i + 1 ensures we never reconsider an element we already decided on, which prevents duplicates.

The unchoose step (current.pop()) is what makes this backtracking rather than just recursion. After exploring all subsets that include nums[i], we remove it and move on to explore subsets that skip nums[i] but might include later elements.

Visual walkthrough

Let's trace through the algorithm with nums = [1, 2, 3]. Watch how each recursive call either includes or skips an element, building up all 8 subsets.

The tree has 2^n leaves (one per subset) and 2^(n+1) - 1 total nodes. Every root-to-leaf path represents a complete sequence of include/skip decisions. The backtracking is visible in steps 5 and 6: after recording [1,2,3], we pop 3 (unchoose), pop 2 (unchoose), and then include 3 without 2 to get [1,3].

The iterative solution

You do not have to use backtracking. There is a clean iterative approach: start with [[]], and for each element, take every existing subset and create a new subset by adding the current element to it.

def subsets(nums: list[int]) -> list[list[int]]:
    result = [[]]

    for num in nums:
        result += [subset + [num] for subset in result]

    return result

This works because each element doubles the number of subsets. Start with [[]]. After processing 1, we have [[], [1]]. After processing 2, we have [[], [1], [2], [1,2]]. After processing 3, we have all 8 subsets.

The iterative approach is concise and avoids recursion, but it does not teach you the choose-explore-unchoose template. In interviews, the backtracking version is usually what the interviewer wants to see because it generalizes to harder problems (Subsets II with duplicates, Combination Sum, Permutations). The iterative version is worth knowing as an alternative, but the backtracking version is the one to drill.

Complexity analysis

Time is O(n * 2^n). There are 2^n subsets, and copying each subset into the result takes up to O(n) time. The recursive tree has 2^n leaves and about 2^(n+1) nodes total, with O(1) work at each node (excluding the copy). So the dominant cost is the 2^n copies of average length n/2, which is O(n * 2^n).

Space is O(n * 2^n) for storing all the subsets in the result. The recursion stack uses O(n) additional space (the maximum depth of the tree), but that is dwarfed by the output size. If we ignore the output, the extra space is just O(n).

Edge cases

Before submitting, check these:

• Empty array: nums = []. Should return [[]]. The empty set is always a subset.
• Single element: nums = [1]. Should return [[], [1]].
• Already sorted vs unsorted: The problem does not require subsets to be in any particular order, but the backtracking approach naturally produces them in a consistent order.
• Large n: With n = 20, there are over a million subsets. The algorithm handles it, but be aware of the exponential growth.

The building blocks

This problem is built on one core reusable piece that CodeBricks drills independently.

Choose-explore-unchoose (backtracking template)

The same skeleton that powers Word Search and every other backtracking problem:

def backtrack(state):
    if is_solution(state):
        record(state)
        return

    for choice in candidates(state):
        make_choice(choice)      # choose
        backtrack(state)          # explore
        undo_choice(choice)       # unchoose

In Subsets, make_choice is current.append(nums[i]). backtrack recurses with i + 1. undo_choice is current.pop(). The twist compared to Word Search is that we record at every node, not just at leaves. The template is identical. The only thing that changes between backtracking problems is what constitutes a "choice" and when you record a result.

This same template handles:

• Subsets II (with duplicates): same code, but sort the input and skip consecutive duplicates in the loop.
• Permutations: instead of range(start, n), iterate over all unused elements.
• Combination Sum: allow reuse by recursing with i instead of i + 1.
• N-Queens: the choice is which column to place the queen in each row.

Once you can write the choose-explore-unchoose skeleton from memory, you can adapt it to any of these problems by swapping in the right candidates and constraints.

Common mistakes

1. Not copying the current subset. As mentioned above, result.append(current) appends a reference. After all the pop() calls, current is empty, so every entry in your result is []. Use current[:] or list(current).

2. Using range(0, len(nums)) instead of range(start, len(nums)). Starting from 0 every time means you reconsider elements you already decided on. You will get duplicate subsets like [1, 2] and [2, 1] (which are the same subset), plus subsets with repeated elements.

3. Modifying the input array. Unlike Word Search, you do not need to mark elements as visited. The start index handles that. If you accidentally modify nums, you will get wrong results on the remaining branches.

4. Returning early at some depth. In many backtracking problems, you stop at a specific depth or when a condition is met. In Subsets, you never return early. Every level of the tree is a valid recording point, and the for loop naturally stops when start == len(nums).

When to use this pattern

Look for these signals:

• The problem asks for all combinations, all subsets, or the power set
• You need to enumerate every possible selection from a set
• The problem involves choosing elements without regard to order (subsets, not permutations)
• Constraints mention n is 20 or less, or similar small bounds (hinting at 2^n enumeration)

Problems that use the same backtracking subsets pattern:

• Subsets II (LeetCode 90): same structure with duplicate handling
• Combination Sum (LeetCode 39): subsets where elements can repeat and must hit a target
• Combination Sum II (LeetCode 40): combinations with duplicates and a target
• Permutations (LeetCode 46): all arrangements, not subsets, but same template

From understanding to recall

You understand the decision tree. You see how each element gets an include/skip choice, and how backtracking undoes the choice before moving to the next branch. But can you write the backtracking solution from scratch in under two minutes?

That is what interviews demand. The subsets LeetCode problem looks simple on paper, but under pressure, small details trip people up: forgetting to copy the list, using the wrong loop bounds, skipping the pop(). These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the choose-explore-unchoose template and the subset-specific loop from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "generate all subsets" and the code flows out without hesitation.

The choose-explore-unchoose pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Word Search - Grid backtracking using the same choose-explore-unchoose template. Compare it to Subsets to see how the same skeleton adapts to a grid context.
• Coin Change - Another problem about making choices from a set, but solved with DP instead of backtracking. Useful contrast for understanding when to enumerate vs. optimize.
• Climbing Stairs - The simplest recursion-to-DP problem. Good warm-up before tackling recursive backtracking.

CodeBricks breaks Subsets into its choose-explore-unchoose building block, then drills it independently with spaced repetition. You type the backtracking skeleton from scratch until it is automatic. When a backtracking problem shows up in your interview, you do not think about it. You just write it.