Subsets

def subsets(nums):
    out = []
    def go(i, picks):
        if i == len(nums):
            out.append(picks[:])   # save a copy
            return
        picks.append(nums[i])      # take it
        go(i + 1, picks)
        picks.pop()                # backtrack
        go(i + 1, picks)           # leave it
    go(0, [])
    return out

Subsets. Given a list of distinct numbers, return every possible subset, including the empty one.

Take one, two, three. There are eight subsets: empty; one; two; three; one two; one three; two three; and one two three.

Recursion makes this simple. For each number there are only two choices: take it, or leave it. Make the choice for the first number, then ask the same question about the rest of the list. When no numbers are left, the choices you made form one subset.

Draw it as a tree. At the top, nothing is chosen. Branch on one: take it or leave it. Each branch splits again on two, then on three. Three levels of yes or no give eight leaves, one for every subset.

In code, a helper takes a position and the current picks. If the position is past the end, save a copy. Otherwise, add the number, recurse, remove it, and recurse again without it. That remove step is the backtrack: it undoes the choice, so the other branch starts clean.

Let's follow the paths. Take one, take two, take three: save one two three. Back up, leave three: one two. Back up twice, leave two, take three: one three. Leave three: just one. Then the same again without one, until the last path leaves everything: the empty set.

There are two to the n subsets, each up to n long, so the time is n times two to the n. The recursion is only n deep.

Take it or leave it, all the way down. That's Subsets.