Generating Subsets

#How does it work?

A set of n elements has 2ⁿ subsets, because each element has two options: it is either in the subset or not. These choices form a binary decision tree.

With backtracking, each level decides on one element. First the element is taken and we continue with the rest; when that branch is done the element is removed (undone) and the branch without it is tried. Every leaf of the tree is a subset.

The same pattern becomes a powerful tool once constraints are added: when looking for subsets with a given sum, a branch whose sum is already too large is never expanded (pruning).

#Try it yourself

#Step by step

1. 01Start at the first element with an empty chosen list.
2. 02Add the element to the list and move to the next element.
3. 03When that branch is done, remove the element and continue without it.
4. 04When every element has been decided (a leaf), record the list as a subset.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def subsets(items: list) -> list:
    out, chosen = [], []

    def visit(i: int) -> None:
        if i == len(items):
            out.append(list(chosen))
            return
        chosen.append(items[i])  # take items[i]
        visit(i + 1)
        chosen.pop()             # leave it (backtrack)
        visit(i + 1)

    visit(0)
    return out


for s in subsets([1, 2, 3]):
    print("{" + ", ".join(map(str, s)) + "}")

#Complexity

Writing each subset takes O(n), so the total is O(n · 2ⁿ); the output itself is that large, so nothing can be faster. Alternatively the numbers 0 to 2ⁿ − 1 can serve as bit masks: if bit i is 1, element i is in the subset.

#When to use it?

Small problems where every combination must be tried: subset sum, team selection, feature selection, combinatorial testing and puzzle search. As n grows, 2ⁿ explodes, so pruning or DP becomes necessary.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• N-Queens
• Generating Permutations