AI Hints
Home›DSA in Python Tutorial›Backtracking
DSA in Python · Lesson 98 of 132

Subsets

Every combination.

⏱ 2 min read▶ Video at 1:57:24🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Subsets
From the video: Subsets
  • 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.

subsets.pypython
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)
Output
[]
['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.

keyvalue
Subsets2ⁿ
Arrangementsn!
10 items1,024 subsets
itertoolscombinations, 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
Next up: Practice: Combination Sum — hitting a target