Python Program to Find All Subsets of a Set

Lists every subset of a list's items (the power set) by deciding for each item in turn whether to include it or skip it.

A subset is any selection of a set's items, from none of them to all of them, where order doesn't matter. All the subsets together are the power set. Each item is either in a subset or not, so 3 items have 2 × 2 × 2 = 8 subsets: [], [1], [2], [3], [1, 2], [1, 3], [2, 3] and [1, 2, 3].

The program finds them by backtracking: it goes through the items one by one, and for each one it first includes it and explores every choice for the items after it, then undoes that and explores them again without it.

Program

def subsets(items):
    """Every subset of items, as a list of lists."""
    result = []
    current = []

    def backtrack(index):
        if index == len(items):
            result.append(current.copy())
            return
        current.append(items[index])  # include this item
        backtrack(index + 1)
        current.pop()                 # undo, then skip it
        backtrack(index + 1)

    backtrack(0)
    return result


for subset in subsets([1, 2, 3]):
    print(subset)

Open in the editor Download subsets.py

Output

[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]
[]

How it works

Visualize Step through the program line by line: each step below shows up as its line runs.

1. result collects the subsets, and current is the subset being built.
2. backtrack(index) decides about items[index]; the items before it are already decided. It's a function inside subsets, so it can use result and current (scope). When index reaches the end, every item has been decided and current is a finished subset: a copy goes into result, because current itself will keep changing.
3. The first choice: include the item, and let the next call decide about the items after it.
4. Then the choice is undone, by taking the item off current again, and the next call explores the other choice: every subset without it.
5. The first call starts at the first item with an empty subset. When it returns, every subset is in result.
6. The program prints every subset of [1, 2, 3], one per line.

Each subset comes from one set of choices, and they come out in this order because including comes first:

Time and space complexity

Every item doubles the number of subsets, so n items have 2ⁿ of them: 8 for 3 items, 1,024 for 10, over a million for 20. Each finished subset is copied into result in up to n steps, so the time is O(n × 2ⁿ). Besides the result, current holds at most n items and the calls go n deep, so the extra space is O(n). The result itself holds n × 2ⁿ⁻¹ items in all, since each item is in half of the subsets.

Other ways to write it

With itertools.combinations()

combinations(items, size) gives every subset of one size, as tuples. Going through every size from 0 to n gives the whole power set, smallest subsets first (modules).

from itertools import combinations

items = [1, 2, 3]
result = []
for size in range(len(items) + 1):
    result.extend(combinations(items, size))
print(result)

With binary numbers

Counting from 0 to 2ⁿ − 1 goes through every pattern of include and skip: bit i of the number says whether items[i] is in. mask >> i & 1 reads that bit. 5 is 101 in binary, so it stands for [1, 3].

def subsets(items):
    result = []
    for mask in range(2 ** len(items)):
        subset = [x for i, x in enumerate(items) if mask >> i & 1]
        result.append(subset)
    return result

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

Try it yourself

• Add a fourth item and check that there are 16 subsets.
• Swap the two choices, so each item is skipped first and included after: the subsets come out in the reverse order, starting with [].
• Save current only when it holds 2 items, to list the combinations of 2.
• Print only the subsets whose items add up to 5: a first step towards the subset sum problem.

More backtracking programs

• Python Program to Print All Permutations Intermediate
• Python Program to Solve the N-Queens Problem Advanced