Backtracking (Systematic Exploration with Undo Strategy)

Systematic backtracking means every recursive branch has a clear invariant (what is fixed so far) and a measure of progress toward a goal or exhaust.

Why this shows up in the real world

Puzzle games, constraint solvers, and interview combinatorial search all share the same skeleton: build state, recurse, undo.

Core idea (explained for students)

Enumerate choices in a fixed order to avoid missing combinations; when a constraint fails, return immediately (fail fast) instead of deepening.

Try this in Python

def subsets(nums: list[int]) -> list[list[int]]:
    res: list[list[int]] = []

    def dfs(i: int, cur: list[int]) -> None:
        if i == len(nums):
            res.append(cur.copy())
            return
        dfs(i + 1, cur)
        cur.append(nums[i])
        dfs(i + 1, cur)
        cur.pop()

    dfs(0, [])
    return res


print(subsets([1, 2]))

Common mistakes

• Infinite recursion when progress measure never increases.
• Global variables without reset between test cases in runners.

Key takeaways

• Template: def dfs(i, state): where i indexes the next decision.
• Log state snapshots only on small inputs when debugging.