Subsets: The Backtracking Template Every Interview Tests

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.

Intuition

Every subset is a sequence of yes/no decisions, one per element. With n elements you get 2^n possible decision strings, which is exactly the size of the power set. Backtracking walks that decision tree depth first, recording the current path at every node. The “start index” version is equivalent: at depth d, you choose which of the remaining elements (if any) to append next. Either framing produces every subset exactly once, and neither can do better than O(2^n) because the output itself is that large.

The bitmask variant skips recursion entirely. Each integer from 0 to 2^n - 1 is itself a yes/no vector, so iterating that range is the same enumeration in a flat loop.

Explanation with 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.

                       []
        +-------------+-------------+
      [1]            [2]           [3]
     /    \           |
  [1,2]  [1,3]      [2,3]
    |
 [1,2,3]

Each node records its own path before extending.

mask  bits   subset
----  ----   --------
0    000    []
1    001    [1]
2    010    [2]
3    011    [1,2]
4    100    [3]
5    101    [1,3]
6    110    [2,3]
7    111    [1,2,3]

Code

Two details matter in the backtracking version: append path.copy() (not the live reference), and record before the loop so the empty subset is captured. The bitmask version is the iterative equivalent.

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


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

import java.util.*;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(nums, 0, path, result);
        return result;
    }

private:
    void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result) {
        result.push_back(path);
        for (int i = start; i < (int)nums.size(); i++) {
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.pop_back();
        }
    }
};

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, 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: same template with a skip-duplicates step after sorting.
• Permutations: backtracking with a “used” set instead of a start index.
• Combinations: backtracking with a fixed combination length.
• Combination Sum: backtracking with reuse and a target sum.
• Letter Combinations of a Phone Number: 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.