Python problem 27 of 30

All subsets

Python
Hard

Write subsets(xs) that returns every subset of a list of distinct items (its power set), without using itertools.

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

Show hint

Start with just the empty subset. For each new item, every subset you already have can either leave it out or take it.

Show solution

def subsets(xs):
    result = [[]]
    for x in xs:
        result += [s + [x] for s in result]
    return result

Each item doubles the number of subsets, so a list of n items has 2ⁿ subsets, and any algorithm that lists them all takes at least that long. This is why brute-force "try every combination" solutions stop working beyond about 25 items.

Another way to see it: count from 0 to 2ⁿ − 1 in binary, and each bit says whether to include one item.

Want a problem like this every day? See today's problem and keep a streak going.