Subsets

Subsets asks for the power set — every possible subset of a list. It is the gateway to backtracking, the technique behind permutations, combinations, and most "generate all possibilities" problems.

The slow way first

You could try to build subsets by size: first all subsets of size 0, then size 1, then size 2, and so on. That works, but the bookkeeping is fiddly and easy to get wrong. The deeper observation is that a subset is just a sequence of yes/no decisions — for each element, is it in or out?

With n elements there are n independent decisions, so there are 2 × 2 × … × 2 = 2ⁿ subsets. No algorithm can beat that count — there are simply that many answers to produce. The goal is to generate them cleanly.

The idea: a decision tree

Think of the choices as a tree. Start with the empty subset. For each element in turn, branch two ways: skip it (go left) or take it (go right). After all n elements have been decided, the path from the root spells out one subset. The leaves are the subsets — and we record the path at every node, so the empty subset and partial subsets are captured too.

The trick that makes this efficient to write is backtracking: we keep a single path list, push an element before recursing, and pop it after. One list is reused for the whole tree instead of copying it at every branch.

Walk through it

Step through the animation. The pointer starts at the root (the empty subset) and recurses down the tree. Each left edge skips an element; each right edge takes it. Watch path grow as we descend and shrink when we pop and backtrack. Every node we visit adds its path to result. By the time we have visited all 8 nodes, result holds the full power set.

Pseudocode

result = empty list
define backtrack(start, path):
    record a COPY of path into result      # every node counts
    for i from start to end of nums:
        add nums[i] to path                # take it
        backtrack(i + 1, path)             # decide the remaining elements
        remove nums[i] from path           # undo — try the next choice
call backtrack(0, empty path)
return result

The Python solution

def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])      # record every node
        for i in range(start, len(nums)):
            path.append(nums[i])    # take nums[i]
            backtrack(i + 1, path)  # decide the rest
            path.pop()              # undo (backtrack)
    backtrack(0, [])
    return result

• result.append(path[:]) records a copy of the current path. Without [:] you would store a reference to the one list that keeps changing — every entry would end up empty.
• The loop starts at start, not 0, so we only ever look forward. That is what prevents duplicates like [2, 1] and [1, 2] both appearing.
• path.append then backtrack(i + 1, path) then path.pop() is the take → recurse → undo rhythm at the core of every backtracking solution.
• Every recursive call records the node it is at, so the empty subset, every partial subset, and the full set are all collected.

Complexity

There are 2ⁿ subsets and copying each one into the result costs up to O(n), so total time is O(n · 2ⁿ). The extra space (beyond the output) is O(n) for the recursion depth and the path list.

When this pattern shows up

Practice