Backtracking (Classic DFS over Choices)

Classic backtracking explores a decision tree depth-first: choose an option, recurse, then undo the choice so siblings can try alternatives.

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)

Represent partial solution as mutable structures (list path, board rows). On exit from recursion, pop or reset the last move so the stack frame’s siblings see a clean slate.

Try this in Python

def permute(nums: list[int]) -> list[list[int]]:
    out: list[list[int]] = []

    def dfs(path: list[int], used: set[int]) -> None:
        if len(path) == len(nums):
            out.append(path.copy())
            return
        for i, x in enumerate(nums):
            if i in used:
                continue
            used.add(i)
            path.append(x)
            dfs(path, used)
            path.pop()
            used.remove(i)

    dfs([], set())
    return out


print(permute([1, 2]))

Common mistakes

• Forgetting to undo after a failed branch—silent duplication of choices.
• Copying entire state each call—O(n) extra cost per level.

Key takeaways

• Draw the decision tree for n≤3 to see where pruning triggers.
• Prefer in-place mutation + undo over deep copying when safe.