Subsets (Backtracking)

The question

You are given a list of distinct numbers. Return every possible subset, including the empty set and the full set.

Explain it to a ten-year-old

You have three toys and a bag. How many different ways can you pack the bag? For each toy you make one choice: put it in, or leave it out. Three toys, two choices each, eight bags. To list them all without missing any, go toy by toy. Put the first toy in, then decide about the second, then the third, write down the bag. Now take the last toy out and try the other choice. Keep undoing your last choice and trying the other way until you have tried everything. That “try, write down, undo, try the other way” is backtracking.

flowchart TB
  r["[ ]"] --> a["[1]"]
  r --> b["[ ] skip 1"]
  a --> a1["[1,2]"]
  a --> a2["[1] skip 2"]
  b --> b1["[2]"]
  b --> b2["[ ] skip 2"]
  note["each leaf is one subset<br/>n items → 2ⁿ leaves"]
  b2 --> note
  style note fill:#fed7aa,stroke:#ea580c

The trick

One recursive function with a current path. At each index, record the path as a subset, then for every later index, add it, recurse, remove it. The remove is the backtrack. Forgetting it is the bug everyone writes first.

The steps

1. out = [], path = [].
2. walk(start): append a copy of path to out.
3. For i from start to the end: append a[i] to path, call walk(i + 1), pop from path.
4. Call walk(0).

def subsets(a):
    out, path = [], []
    def walk(start):
        out.append(path[:])
        for i in range(start, len(a)):
            path.append(a[i])
            walk(i + 1)
            path.pop()
    walk(0)
    return out

Time O(n × 2ⁿ), there are 2ⁿ subsets and copying each costs up to n. You cannot beat the output size.

In GPU infrastructure

Choosing which GPUs to include in a burn-in test set is subsets over eight GPUs on a host, and all 256 combinations is exactly what I want when hunting an intermittent XID error that only appears with certain pairs. The same backtracking builds the list of NIC subsets for a partial RDMA test when one link is suspect and I want every combination that includes it. I never enumerate subsets of the whole fleet, and I expect you to say why: two to the thousand does not fit anywhere. The pop after the recursive call is the line people forget, and a test plan without it lists the same eight GPUs over and over.

What I am listening for

• The path[:] copy. Without it every entry in out is the same list.
• The pop. Without it the path never shrinks.
• The cousins: permutations, combinations of size k, subsets with duplicates. Same walk, one extra rule each. If you can name one, I stop asking.

Go deeper

• The technique: Backtracking on Wikipedia
• The problem statement: Subsets on LeetCode

With AI on the table. The tool writes the walk. I ask how many subsets a list of forty items has and whether your program will finish. A trillion. It will not. Knowing when not to run the code is a skill too.