Generating All Subsets

The cleanest recursive formulation is: the subsets of a list are the subsets that do not contain the first element, plus the subsets that do, with the first element added to each of them. That gives a direct recursion with a single base case, the empty list, whose only subset is the empty set.

An equivalent iterative version starts with a single empty subset and, for each element, adds a copy of the current list of subsets with that element appended. Both produce the same set of answers.

The complexity is the interesting part. A list of n elements has exactly two to the power n subsets, so any algorithm that returns them all must do at least that much work just to produce the output. The recursive version runs in O of n times two to the power n time, because there are two to the power n calls and each one does an amount of work proportional to the size of the subset it is copying. The bitmask version runs in O of n times two to the power n as well, because it scans every element for every mask.

The trade-off to name is that the output size dominates everything, so the cleverest possible constant factors barely matter. What does matter is whether you materialise the whole answer set or generate it lazily. A generator that yields one subset at a time uses O of n space instead of O of n times two to the power n, which is the right answer when the caller only needs to count them or stop early.

Represent each subset by an integer whose bits say which positions are included. Loop over every mask from zero to two to the power n minus one, and for each mask collect the elements whose bit is set.

def subsets(values):
    result = []
    for mask in range(1 << len(values)):
        group = [values[i] for i in range(len(values)) if mask & (1 << i)]
        result.append(group)
    return result


print(subsets([1, 2, 3]))

The output is eight subsets: the empty one, then 1, then 2, then 1 and 2, then 3, then 1 and 3, then 2 and 3, then 1, 2 and 3. Every subset appears exactly once, because every subset corresponds to exactly one bit pattern.

The mechanism is a bijection between subsets and bit patterns. There are n bits, each either on or off, so there are two to the power n patterns, which is exactly the number of subsets. The mask ordering also gives you a stable, deterministic sequence rather than the more arbitrary order a recursive generator produces.

The trade-off to name is that this is elegant but not especially fast, because for every mask it rescans all n positions. A recursive generator that maintains a growing list of choices avoids that rescan and is usually the better choice for larger inputs. The bitmask version earns its place because it is short, obvious, and handles the empty subset for free. It also scales to the variant where you want the subsets of a set of size thirty or so, where the count is over a billion and the only sensible approach is to iterate lazily.