Subsets

The recursive code for subsets is short. The reasoning behind it is the part worth learning: every input element creates one independent choice—include it or exclude it.

Read the output contract first

The problem gives an array nums containing unique integers and asks for every possible subset:

• The empty subset [] is valid.
• The full array is valid.
• No subset may appear twice.
• The order of the returned subsets does not matter.
• The order of elements inside a subset follows the input order in our implementation.

For nums = [1, 2, 3], the result contains eight subsets:

[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]

This complete collection is called the power set. The name matters less than the contract: select any combination of the input elements, including selecting none.

The first useful observation is the count. Each element has two possibilities:

• It is included.
• It is excluded.

With three elements, that gives:

2 choices × 2 choices × 2 choices = 2^3 = 8

The supplied constraints keep n small—1 <= n <= 10—but the underlying pattern is general. If the problem asks you to return all subsets, you must account for exponential output because the output itself contains 2^n entries.

Spot the include/exclude pattern

The decisive recognition cue is simple:

Every item contributes an independent yes-or-no decision, and the problem asks for every completed combination of those decisions.

That points directly to include/exclude recursion.

Imagine processing [1, 2]. At index 0, decide what to do with 1:

                         decide about 1
                         /             \
                   exclude 1         include 1
                       /                 \
                decide about 2      decide about 2
                 /        \           /        \
             exclude    include    exclude    include
                []        [2]         [1]       [1, 2]

Every leaf represents one complete sequence of decisions. Every sequence produces one subset.

This is exhaustive enumeration, but that is not a criticism. The problem explicitly asks for all possibilities. There is no hidden polynomial-time shortcut that can return the complete list without producing those possibilities. The right goal is to avoid unnecessary repeated work while exploring the required decision space once.

This is the core of subsets backtracking: build one candidate, explore it, then restore the state so the next branch starts cleanly.

Define the recursive state

Let the helper function be:

backtrack(i)

It processes the element at index i.

We maintain two pieces of state:

• current: the subset currently being built.
• result: all completed subsets found so far.

The key invariant is:

Before processing nums[i], current contains exactly the selected elements from the already processed prefix nums[0:i], in input order.

That sentence gives the recursive function its meaning. It also tells us what each branch must do.

For nums[i], there are two transitions:

1. Exclude nums[i]
   Leave current unchanged and recurse to i + 1.

2. Include nums[i]
   Append it to current, recurse to i + 1, then remove it before returning.

The removal is the backtracking step. It restores current to the state it had before the include decision.

The base case is:

i == len(nums)

At that point, every element has received a decision. current is therefore one complete subset, so we store it in result.

There is one important Python detail: store a copy of current.

A list is mutable. If you append current itself, every entry in result refers to the same list object. Later append and pop operations will change previously stored answers. The snapshot must be independent:

result.append(current[:])

Two bugs appear repeatedly in this problem:

• Forgetting pop() causes an included element to leak into sibling branches.
• Storing current without copying causes old answers to change when the recursion keeps mutating the list.

The state has a simple lifecycle:

append → recurse → pop

The append and pop must balance like opening and closing a bracket.

Why every subset appears exactly once

A passing example is useful, but the proof explains why the method works for every valid input.

Coverage

Take any subset of nums. For each input position, that subset either:

• includes the element at that position, or
• excludes it.

So every subset corresponds to one binary decision sequence of length n.

The recursion explores both choices at every position. Therefore, it explores the decision sequence corresponding to every possible subset.

The all-exclude sequence is especially important:

exclude 1
exclude 2
exclude 3

It reaches the base case with current == []. That is why the empty subset appears automatically. No special-case append is needed.

Uniqueness

Because the input elements are unique, each position represents a distinct choice. A decision sequence is determined by which positions were included.

Two different decision sequences must differ at some position. At that position, one sequence includes the element and the other excludes it. They therefore produce different subsets.

So:

• Every valid subset is covered.
• No subset is produced twice.

The output order depends on whether we explore exclude or include first, but the contract allows any order.

The Python implementation

Here is the complete backtracking solution. The code follows the derivation directly: define the base case, explore exclusion, explore inclusion, restore the state, then start at index 0.

from typing import List


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        current = []
        n = len(nums)

        def backtrack(index: int) -> None:
            # Every element has been classified.
            if index == n:
                result.append(current[:])
                return

            # Choice 1: exclude nums[index].
            backtrack(index + 1)

            # Choice 2: include nums[index].
            current.append(nums[index])
            backtrack(index + 1)

            # Restore current for the caller's next branch.
            current.pop()

        backtrack(0)
        return result

The initial call, backtrack(0), means that no input elements have been processed and current is empty.

A short trace

Use nums = [1, 2, 3]. The recursion first explores the exclude branch for each element:

current = []
exclude 1
  exclude 2
    exclude 3
      leaf: append []

It then returns and explores the include branch for 3:

current = []
exclude 1
  exclude 2
    include 3
      current = [3]
      leaf: append [3]
      pop 3
      current = []

Next, the recursion includes 2:

current = []
exclude 1
  include 2
    exclude 3
      current = [2]
      leaf: append [2]
      current = [2] after return
    include 3
      current = [2, 3]
      leaf: append [2, 3]
      pop 3
      current = [2]
    pop 2
    current = []

Notice the restoration:

• After exploring [2, 3], pop() returns current to [2].
• After finishing the entire 2 branch, another pop() returns it to [].
• The next branch can now make an independent decision about 1.

When reviewing your implementation, check these two lines first:

result.append(current[:])  # snapshot at the leaf
current.pop()              # restore after inclusion

They protect the two most common mutable-state failures.

Iterative and bit-mask alternatives

The same power-set model can be represented without recursive calls.

Iterative expansion

Start with the only subset available before processing any values:

[[]]

For each value, copy every existing subset and append the new value to the copy.

For example, with [1, 2]:

start with: [[]]

process 1:
existing: [[]]
new:      [[1]]
result:   [[], [1]]

process 2:
existing: [[], [1]]
new:      [[2], [1, 2]]
result:   [[], [1], [2], [1, 2]]

The crucial detail is that the new subsets must be generated from the existing portion for the current iteration. If you keep extending the same list while iterating over it, you can accidentally process newly created subsets again in that same pass.

This method is often a good choice when you want to avoid recursion and the “double the list” idea is easier to explain than a decision tree.

Bit-mask enumeration

A subset can also be represented by an n-bit number.

For nums = [1, 2, 3]:

mask 000 → []
mask 001 → [1]
mask 010 → [2]
mask 011 → [1, 2]
mask 100 → [3]
...
mask 111 → [1, 2, 3]

Bit i records whether nums[i] is selected:

• 0 means exclude it.
• 1 means include it.

Enumerating masks from 0 through 2^n - 1 therefore enumerates every subset exactly once.

My interview preference is to start with recursive backtracking when the include/exclude tree is the clearest explanation. Use iterative expansion when avoiding recursion matters. Use bit masks when binary selection is already the natural representation of the problem.

These are different implementations of the same combinatorial fact. The representation changes; the 2^n possibilities do not.

Complexity and edge cases

There are exactly 2^n subsets. Any solution that returns them must materialize that many result entries.

The usual materialized-output analysis is:

• Time: O(n * 2^n)
• Auxiliary working space: O(n)
• Total space including the returned result: O(n * 2^n)

Why does time include the factor of n? The recursion has 2^n leaves, but storing each leaf requires copying its current subset. A subset can contain up to n elements, so the copying work contributes the additional factor.

The recursion path and the mutable current list each use at most O(n) space. The returned list is much larger and must be counted separately when discussing total memory.

Check these cases:

Input	Required shape	What it verifies
[0]	[[], [0]] in any order	The empty choice is included
[1, 2]	Four subsets	Both branches are explored
[1, 2, 3]	Eight subsets	The 2^n count holds
Any unique input	No duplicate subsets	Each position is decided once

The uniqueness condition is part of this problem's contract. If the input can contain duplicates, the same include/exclude code may produce duplicate value-lists. Removing those duplicates requires a different design, commonly called the “Subsets II” variant. Do not silently mix that problem into this one.

The transferable rule

When every item contributes an independent yes-or-no choice and the problem asks for every valid selection, create one decision per item.

Then make the recursion answer one precise question:

Which choices have I made so far, and what remains undecided?

A leaf means every decision is complete. Store a snapshot. Restore mutable state before returning.

For this Subsets solution, the interview checklist is:

• Define the base case at index == n.
• Explore both exclude and include branches.
• Copy the current path at the leaf.
• Pop after the include branch.
• Let the all-exclude path produce [].
• Prove coverage and uniqueness from the decision sequence.
• Account for 2^n outputs and O(n * 2^n) materialization work.

That pattern transfers directly to many combinatorial-generation problems. Clear the state. Make the choice. Explore the branch. Restore the state. Let a complete path become one answer.