LeetCode Subsets: The Backtracking Template Every Interview Tests

LeetCode 78, Subsets, is the foundational backtracking problem. Once you internalize its include-or-exclude template, Combinations, Permutations, Subsets II, and Combination Sum become straightforward variants. Interviewers reach for this problem because it forces you to demonstrate clean recursion, careful list copying, and confident complexity reasoning all in one short solution.

The Problem

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets, and you may return the subsets in any order.

Example inputs and outputs:

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

Input:  nums = [0]
Output: [[], [0]]

Input:  nums = []
Output: [[]]

For an array of length n, the power set has exactly 2^n subsets, because each element independently is either in or out of a subset. That observation is the basis for both the backtracking and bitmask solutions.

Brute Force

There is no asymptotically better solution than O(2^n) because the output itself is that large. The “brute force” framing here is the natural nested-loop attempt, which only works for fixed small n:

def subsets_brute(nums: list[int]) -> list[list[int]]:
    # Only correct for n = 3.
    result = []
    for a in (False, True):
        for b in (False, True):
            for c in (False, True):
                subset = []
                if a: subset.append(nums[0])
                if b: subset.append(nums[1])
                if c: subset.append(nums[2])
                result.append(subset)
    return result

This does not generalize, which motivates a recursive solution.

Optimal Solution

Backtracking with the include-or-exclude template:

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

    def backtrack(start: int) -> None:
        result.append(path.copy())
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Two details matter:

1. We append path.copy(), not path itself. Appending the live reference would mean every entry in result ends up mutated to the final state of path.
2. We append before the loop, not after. This guarantees we record every prefix path, including the empty subset.

An equally clean iterative version uses bitmasks:

def subsets_bitmask(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result

For each integer mask from 0 to 2^n - 1, bit i of mask decides whether nums[i] is included. This is often the version interviewers reach for when they want to avoid recursion.

Walk Through an Example

Take nums = [1, 2, 3]. The recursion tree built by backtracking, in call order:

backtrack(0)  path=[]            -> record []
  i=0 path=[1]
    backtrack(1)                 -> record [1]
      i=1 path=[1, 2]
        backtrack(2)             -> record [1, 2]
          i=2 path=[1, 2, 3]
            backtrack(3)         -> record [1, 2, 3]
      i=2 path=[1, 3]
        backtrack(3)             -> record [1, 3]
  i=1 path=[2]
    backtrack(2)                 -> record [2]
      i=2 path=[2, 3]
        backtrack(3)             -> record [2, 3]
  i=2 path=[3]
    backtrack(3)                 -> record [3]

All eight subsets are produced exactly once. The recursion tree has depth n and the work done at each node is O(n) for the copy, matching the complexity we will derive below.

Edge Cases

• Empty input: return [[]]. The recursion records the empty subset before any loop iteration.
• Single element: return [[], [nums[0]]].
• Already sorted or reverse sorted input: the algorithm does not care about order; output order will differ.
• Duplicates in input: this problem specifies unique elements. If duplicates are present, see Subsets II (LeetCode 90), which adds a “skip duplicates at the same recursion level” guard.
• Very large n: with n = 20, output already contains over a million subsets. The bottleneck becomes memory, not algorithmic time.

Complexity Analysis

• Time: O(n * 2^n). There are 2^n subsets and each one costs up to O(n) to construct.
• Space: O(n * 2^n) for the output. The recursion stack itself is only O(n).

This is optimal because the output size is itself O(n * 2^n) characters in the worst case. You cannot beat the output. If you want a refresher on why exponential growth dominates polynomial growth so dramatically, see /blog/big-o-notation-explained.

How to Explain It in an Interview

Use this script:

1. Note that the output has exactly 2^n elements because each element is independently in or out.
2. Pick backtracking and describe the include-or-exclude template.
3. Emphasize the path.copy() step. Many candidates fail by appending the live reference.
4. Walk through the recursion tree for [1, 2, 3] to demonstrate correctness.
5. State the complexity as O(n * 2^n) and explain the n factor as the cost of building each subset.
6. Offer the bitmask version as the iterative alternative if asked.

Interviewers like to hear that “backtracking is DFS over the decision tree.” That framing connects the problem to the broader graph traversal vocabulary; see /blog/graphs-introduction if that connection is new to you.

Related Problems

• Subsets II (LeetCode 90): same template with a skip-duplicates step after sorting.
• Permutations (LeetCode 46): backtracking with a “used” set instead of a start index.
• Combinations (LeetCode 77): backtracking with a fixed combination length.
• Combination Sum (LeetCode 39): backtracking with reuse and a target sum.
• Letter Combinations of a Phone Number (LeetCode 17): same template applied to letters.

Wrap up

Subsets is the gateway to the entire backtracking family. The include-or-exclude template, the path.copy() discipline, and the bitmask alternative are all the moving parts you need to solve Permutations, Combinations, and N-Queens variants with confidence. Practice writing the recursion and the bitmask side by side until you can produce either on demand, then pair this with /blog/recursion-fundamentals to keep your recursion intuition sharp.