Subsets
Every combination.
Given a few toppings, cheese, ham, and olives, how many different pizzas can you make, including a plain one? For each topping, you either add it, or you don't. That yes or no choice is perfect for backtracking.

- Cheese, ham, olives
- Add it, or not
- Yes or no for each
Include or exclude
At each position, we explore two branches. First, without this topping. Then, with it, adding it to the path, exploring, and removing it again. When we've decided on every topping, the path is one complete pizza. Run it. Eight pizzas, which is two to the power of three.
def subsets(items):
results, path = [], []
def explore(i):
if i == len(items):
results.append(list(path))
return
explore(i + 1)
path.append(items[i])
explore(i + 1)
path.pop()
explore(0)
return results
for s in subsets(["cheese", "ham", "olives"]):
print(s)[] ['olives'] ['ham'] ['ham', 'olives'] ['cheese'] ['cheese', 'olives'] ['cheese', 'ham'] ['cheese', 'ham', 'olives']
Counting the cost
With N items, there are two to the N subsets. Ten items give a thousand and twenty four. Thirty items give over a billion. That's why backtracking must stay small, or cut branches early. Python's itertools module also has combinations and permutations, ready made.
| key | value |
|---|---|
| Subsets | 2ⁿ |
| Arrangements | n! |
| 10 items | 1,024 subsets |
| itertools | combinations, permutations |
Summary
For subsets, explore each item twice, with and without it. There are two to the N results. Next, backtracking with a target to hit.
Key takeaways- Without it
- With it
- 2ⁿ subsets