Subsets: take it or leave it

Which toppings could go on a pizza? Which of your songs fit on a 60-minute playlist? In what order could five friends sit at a table? Questions like these have no clever formula: a program has to go through the options one by one. For two toppings, two nested loops would do, and for three toppings, three loops. But how many toppings there are is only known when the program runs, and you can't write a loop for each one. A recursive function can do it: one call settles one decision, and a call one level deeper settles the next.

When a call has seen everything that can follow from its decision, it takes the decision back and tries its next option. That is backtracking, and every function in this module is made of the same three moves: choose an option, explore what follows from it with a recursive call, un-choose it.

Take it or leave it

A subset of a list is some of its items, anything from none of them to all of them. Each item is either in or out, so three items give 2 × 2 × 2 = 8 subsets. Drawn as a tree, each level settles one item (the question on the right): taking the item goes left, leaving it out goes right. The bottom row has the 8 subsets:

                    []                      a?
              /            \
           [a]              []              b?
         /     \          /     \
     [a, b]    [a]      [b]      []         c?
     /   \     /  \     /  \     /  \
   abc   ab   ac   a   bc   b   c   (none)

A recursive function walks this tree from left to right:

def explore(items, i, path):
    if i == len(items):
        print(path)
        return
    path.append(items[i])         # choose: take items[i]
    explore(items, i + 1, path)   # explore every subset with it
    path.pop()                    # un-choose
    explore(items, i + 1, path)   # explore every subset without it


explore(["a", "b", "c"], 0, [])

['a', 'b', 'c']
['a', 'b']
['a', 'c']
['a']
['b', 'c']
['b']
['c']
[]

How it works

• The parameter i is the position of the item this call settles. Once i reaches len(items), nothing is left to settle and path is one finished subset, so the call prints it: that's the base case.
• There is only one list, path, shared by all the calls. Taking an item appends it, and path.pop() takes it off again, so the "leave it out" call starts from exactly the path this call was given. That undo is the heart of backtracking: without it, a would still be in the path while the search explores the subsets without a.
• The first four lines all hold a: the search finishes everything below "take a" before it starts on "leave a". The output is the bottom row of the tree, read from left to right.

Saving the subsets: copy the path

To return the subsets instead of printing them, append each complete one to a result list. The obvious line has a trap:

def collect(items, i, path, result):
    if i == len(items):
        result.append(path)
        return
    path.append(items[i])
    collect(items, i + 1, path, result)
    path.pop()
    collect(items, i + 1, path, result)


result = []
collect([1, 2, 3], 0, [], result)
print(result)

[[], [], [], [], [], [], [], []]

Eight empty lists. result.append(path) doesn't store the numbers the path holds right now: it stores a reference to the list path itself, the same list eight times. Every append on path was undone by a pop, so at the end path is empty, and so is every "subset" in the result. Store a copy instead, result.append(path[:]) (or list(path)), and the result is [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []].

What it costs

Every item you add doubles the number of subsets: n items have 2ⁿ of them. The playlist question over 15 songs means 32,768 subsets, over 25 songs about 33 million, and over 40 songs about a trillion. The tree has 2ⁿ⁺¹ - 1 calls in all, and copying a subset takes up to n steps, so collecting every subset is O(n · 2ⁿ) time, and the result needs as much memory. The search itself only keeps the calls on the current path: n + 1 calls deep, O(n) extra memory, far from Python's limit of about 1000 calls. Going through every option like this is called exhaustive search. It's fine for 20 items and hopeless for 50, unless whole branches of the tree can be skipped, as step 3 shows.