LeetCode 78 · Backtracking

Subsets, explained with a picture

Pizza toppings: take it or leave it.

MediumBacktracking
▶ Watch it step by step

The problem

Given a list of distinct numbers, return all possible subsets (including the empty one).

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

Picture it

Picture ordering a pizza. For each topping in turn, you make a yes/no choice: take it or leave it. The picture draws these choices as a decision tree: each level is one topping, each split is take/leave. Every path from the top to the bottom is one complete pizza (one subset). n toppings give 2ⁿ pizzas.

How to recognise it

  • The question asks for all subsets, combinations or arrangements, not for one best answer or a count.
  • Each item has a small yes/no style choice (take it or leave it), and choices at different items do not interfere.
  • The input is tiny (here at most 10 distinct numbers), which hints that the answer set itself is exponential: 2^10 = 1,024 subsets.
  • You can describe the answer as a decision tree: one level per item, one branch per choice, and every path from top to bottom is one answer.
  • That is backtracking: build a partial answer, recurse to make the next choice, then undo the last choice (un-choose) and try the other one.

Start with brute force

Every subset corresponds to a binary number: bit i says whether nums[i] is in. Count from 0 to 2^n − 1 and build one subset per number.

def subsets_brute(nums):
    n = len(nums)
    res = []
    for mask in range(1 << n):
        res.append([nums[i] for i in range(n) if mask >> i & 1])
    return res

This is correct and also fast enough here: 2^n masks times n bit tests, so O(n · 2^n) time, and the output itself holds up to n · 2^n numbers. It cannot be beaten much, because the answer alone has 2^n subsets. What it cannot do is prune: if a problem adds a rule such as "sum must equal a target", the mask loop still builds every subset first. The recursive version below is the same count of work, but it is the shape that lets later problems stop early.

From brute force to the idea

  1. Describe the answer as choices. Walk through the numbers in order. At position i there are exactly two options: take nums[i] or leave it.
  2. Keep one shared partial answer. pick is the list built so far. Taking a number means pick.append(nums[i]).
  3. Recurse, then undo. After exploring everything that follows the "take" branch, pick.pop() removes the number again so the "leave" branch starts from the same state.
  4. Stop at the bottom. When i == len(nums) every number has been decided, so pick is one finished subset.
  5. Copy before saving. pick keeps changing, so store pick[:], a copy.

This is the key idea: choose, recurse, un-choose, with a copy taken at each leaf.

The key idea

Backtracking: at each index branch “include” and “exclude”. 2ⁿ subsets.

Python solution

def subsets(nums):
    res, pick = [], []
    def dfs(i):
        if i == len(nums):
            res.append(pick[:])          # a finished pizza
            return
        pick.append(nums[i])             # take topping i
        dfs(i + 1)
        pick.pop()                       # leave topping i
        dfs(i + 1)
    dfs(0)
    return res

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Bitmask brute forceO(n · 2^n): 2^n masks, n bit tests eachO(n) beyond the output
Take or leave recursion (shown code)O(n · 2^n): 2^n leaves, each copying up to n numbersO(n) beyond the output: recursion depth is n + 1 and pick holds at most n numbers

Edge cases

  • Empty list: returns [[]], one subset (the empty one).
  • One number ([5]): returns [[5], []].
  • Order of the output: taking comes first, so [1, 2, 3] returns [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]], matching the example. LeetCode accepts any order.
  • Maximum size: 10 numbers produce 1,024 subsets, and the recursion is only 11 calls deep.
  • Duplicates in the input: the code would return repeated subsets. The problem promises distinct numbers; problem 90 handles duplicates.
  • Input is not changed.

Common mistakes

  • Appending pick itself instead of pick[:]. Every saved entry is the same list, which ends up empty: subsets([1, 2]) returns [[], [], [], []].
  • Forgetting pick.pop(). The "leave" branch then still contains the number, so subsets([1, 2]) returns [[1, 2], [1, 2], [1, 2, 2], [1, 2, 2]].
  • Starting the recursion at index 1, which skips the first number's choice entirely.
  • Looping inside the recursion without a start index, which produces the same subset in several orders.
Your turn: subsets of exactly k numbers

Return only the subsets that have exactly k numbers (these are called combinations). Describe how you would stop branches that can no longer succeed, then write it if you like.

Compare with our answer

Keep the same take or leave tree and add two rules. Stop when pick already has k numbers (save it). Also stop early when there are not enough numbers left to reach k, since those branches can never produce an answer.

def combinations(nums, k):
    res, pick = [], []
    def dfs(i):
        if len(pick) == k:
            res.append(pick[:])
            return
        if len(pick) + len(nums) - i < k:     # too few numbers left
            return
        pick.append(nums[i])
        dfs(i + 1)
        pick.pop()
        dfs(i + 1)
    dfs(0)
    return res

combinations([1, 2, 3, 4], 2) returns 6 lists. Time is at most O(n · 2^n) and in practice far less, because many branches stop early; space is O(n) beyond the output.

A strong answer mentions: stopping at length k, the "not enough numbers left" pruning, and why the answer count C(n, k) is smaller than 2^n.

Check what stuck

1. A settings screen has 8 independent on/off switches, and a test tool must list every possible combination of them. Which approach fits best?

2. What is the time complexity of the shown code for n numbers, and why?

3. A learner changes res.append(pick[:]) to res.append(pick). What does subsets([1, 2]) return?

Score 60% or more and the lesson is marked complete.