Backtracking Basics

Basics cover partial solutions, choice lists, recursion depth, and the guarantee that every leaf corresponds to a complete or maximal partial build.

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)

Start from “pick or skip” or “try each candidate at position i”. Always ask: what changes between parent and child state?

Try this in Python

def combo_sum(candidates: list[int], target: int) -> list[list[int]]:
    res: list[list[int]] = []

    def dfs(start: int, remain: int, path: list[int]) -> None:
        if remain == 0:
            res.append(path.copy())
            return
        if remain < 0:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            dfs(i, remain - candidates[i], path)
            path.pop()

    dfs(0, target, [])
    return res


print(combo_sum([2, 3], 5))

Common mistakes

• Mixing return value recursion with global collector without clear contract.
• Off-by-one on the index that represents “next empty slot”.

Key takeaways

• Trace one path from root to leaf on paper before coding.
• Write assert invariants during development, strip later.