Home / Python / Example programs / Functions and recursion

Python program: All subsets of a set

List every subset (the power set) of a small set of items.

The code

from itertools import combinations

def subsets(items):
    if not items:
        return [[]]
    rest = subsets(items[1:])
    return rest + [[items[0]] + s for s in rest]

print(subsets(["a", "b", "c"]))
print([list(c) for r in range(4) for c in combinations("abc", r)])

Output

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

How it works

Each subset either leaves out the first item or includes it: that gives the recursion. itertools.combinations generates subsets of each size.

Python features used

Learn the ideas behind it in the free lesson More Functions.