Choose or Skip: Recursion That Builds Subsets
A pizza place offers three extra toppings: olive, onion and pepper. The menu designer wants to print every possible combination, from a plain pizza to one with all three. That is not "find the best one"; it is "list them all", and listing everything is the job of backtracking.
The rule
At each item, branch twice: take it, or leave it.
Walk through the items in order. For each one there are exactly two futures: the pizza has this topping, or it does not. Explore the first future fully, come back, and explore the second. When you run out of items, the choices you made form one complete combination. Recursion expresses this directly:
def all_subsets(items):
result, path = [], []
def explore(i):
if i == len(items): # base case: every item decided
result.append(path[:]) # save a COPY of the current choices
return
path.append(items[i]) # choose: take item i
explore(i + 1)
path.pop() # un-choose: undo it
explore(i + 1) # skip item i
explore(0)
return resultThree parts make every backtracking function:
- The base case stops the recursion: here, when all items are decided.
- Choose, explore, un-choose: change
path, recurse, then undo the change exactly, so the next branch starts from a clean state. - Save a copy:
pathkeeps changing after you record it, so storepath[:], notpathitself.
Recursion itself is just a function solving a smaller copy of the same problem: explore(i) means "decide the items from position i onwards". Each call hands on a problem one item smaller, which is why every branch is guaranteed to reach the base case.
Each item doubles the number of results, so n items give 2ⁿ subsets. That is fine for 20 items (about a million) and hopeless for 40 (about a trillion), which is why backtracking problems come with small limits.
The shortcut
Picture a decision tree: each level is one item, each fork is take-or-leave, and each leaf at the bottom is one finished answer. The recursion is just a walk down the left branch first, then back up and down the right.
Take olive, take onion, take pepper
All three decided: record
[olive, onion, pepper]. Undo pepper.
The trap is forgetting the copy. Store path itself and every saved answer is the same list object, which ends up empty once all the undoing is finished.
Drills
Answer fast — trust the rule.
How many subsets does all_subsets produce for 5 items?
What is the first subset all_subsets(["olive", "onion", "pepper"]) records?
If result.append(path) replaced result.append(path[:]), what would all_subsets(["a", "b"]) return?
A problem asks for every subset of up to 40 items. What should you conclude?
Remember
- At each item, branch twice: take it, or leave it.
- Shortcut: picture the decision tree; choose, explore, un-choose.
- Trap: saving
pathinstead of a copy,path[:].