Lesson 21 — Backtracking: subsets

Backtracking: choose, explore, undo

Backtracking explores every possibility by making a choice, exploring everything that follows, then undoing the choice to try the next one. For subsets: add a number to the current path, recurse, then pop it off.

picked.append(item)   # choose
search(...)           # explore
picked.pop()          # undo

We save a copy of the path (path[:]) because the list keeps changing afterwards.

Why it matters: Sudoku solvers, permutations, timetables and puzzle games are all backtracking.