Backtracking

Backtracking is DFS over a decision tree. At each node: choose a candidate, recurse, un-choose. That symmetric third step lets you reuse one mutable buffer.

Template:

def dfs(state):
    if is_goal(state): record(state); return
    for choice in candidates(state):
        apply(choice)
        dfs(state)
        undo(choice)

Permutations vs subsets

Permutations need a used marker. Branching factor at depth k = n - k. n! leaves.

Subsets are binary at each index: take or skip. 2ⁿ leaves. Generalizes to combinations and combination-sum.

N-Queens flavour

Same skeleton + three pruning sets: occupied columns, occupied row+col diagonals, occupied row-col anti-diagonals. Place row by row.

Common pitfalls

• Appending the live list. out.append(path) stores a reference. Snapshot: path[:].
• Forgetting to un-choose. One missed pop corrupts every sibling branch.
• Duplicate results. Sort input, skip nums[i] == nums[i-1] when i > start.
• Recursion depth. Python's 1000-limit. Bump or iterate.

When to reach for it

Combinatorial objects (arrangements, selections, paths) where constraints prune aggressively. If search space is 2ⁿ or n! with no pruning, need memoization or smarter formulation.

Try it

1. Add k parameter to subsets — only size-k combinations. Prune when len(path) + remaining < k.
2. Write solve_n_queens(n) returning count of valid boards. Expected for n=8: 92.