Framework #1 — Backtracking template: choose-explore-unchoose

BACKTRACKING TEMPLATE
─────────────────────
def backtrack(state, choices):
    if is_goal(state):
        result.append(state[:])  # copy!
        return

    for choice in choices:
        if not is_valid(choice, state):
            continue

        # 1. CHOOSE
        state.append(choice)      # or modify state

        # 2. EXPLORE
        backtrack(state, next_choices)

        # 3. UNCHOOSE (undo mutation)
        state.pop()               # or restore state

CRITICAL POINTS:
  □ Copy state on goal (state[:] or list(state))
  □ Always undo mutations (symmetric choose/unchoose)
  □ Prune early with is_valid before recursing
  □ Track 'start index' for combinations to avoid dupes