Every subset, in order

Given a list of distinct numbers, list every subset, including the empty one and the whole list.

Print one subset per line, values separated by spaces. The empty subset is an empty line. Print them in the order the standard walk produces: for each position in turn, every subset that leaves it out comes before those that include it, reading the list left to right.

Worked example#

For [1, 2, 3], the eight subsets in the order this wants:

(empty)
1
1 2
1 2 3
1 3
2
2 3
3

Read it as a walk of decisions. Take nothing and write that down. Take 1, write it down, then go on from there: 1 and 2, then 1, 2 and 3. Back up and try 1 with 3. Back up again and start from 2. Every line is written the moment the walk reaches it, which is why the empty subset comes first and 1 2 3 comes before 1 3.

The idea#

For each number there are two choices: leave it out, or put it in. Three numbers, two choices each, eight subsets. That doubling is what makes this exponential, and no cleverness avoids it: there really are that many answers.

Backtracking is the way to walk those choices without writing eight separate loops.

walk(position, chosen):
    record chosen
    for i from position to the end:
        chosen.add(nums[i])       # choose
        walk(i + 1, chosen)       # explore
        chosen.remove(last)       # un-choose

Three lines in the loop, and they have names worth learning: choose, explore, un-choose. Every backtracking solution you write will have that shape.

The line everyone forgets#

The un-choose at the end. Without it, chosen keeps everything from the branch you just finished, and the next branch starts from the wrong place. The bug looks like duplicate or oversized answers, and it is the single most common mistake in this whole topic.

It is needed because chosen is one list being shared by every branch. Copy it at each step instead and you can skip the un-choose, at the cost of a copy per node.

Why i + 1 and not position + 1#

Recursing on i + 1 means each number can only be followed by ones after it, so [1, 3] is generated and [3, 1] is not. That is what makes these subsets rather than permutations. Change that one line and you get a different problem, which is worth trying once.

Constraints#

• 1 <= n <= 15, so at most 32768 subsets
• Values are distinct