Backtracking

When to reach for it

• The question asks for every solution, or whether any exists, among combinations or arrangements.
• The words subsets, permutations, combinations, partitions or placements appear.
• Constraint puzzles: filling a grid, placing pieces that must not attack each other, finding words in a letter grid.
• The input is small, often up to 15 or 20 items, which hints that exponential time is expected.

The core idea

Picture a tree of decisions. Each level makes one choice: include this item or not, put this value here, step in this direction. A recursive function carries the partial answer. At each call it tries each available choice, recurses, then undoes that choice before trying the next. The rhythm is always the same: choose, explore, un-choose.

Pruning is what makes it practical. Check constraints as early as possible and return as soon as the partial answer cannot be completed. Sorting the input first often lets you skip duplicates (equal neighbors at the same level of the tree) and stop early once the remaining values are too large.

A Python template

def case_variants(s):
    """Every way to write s with each letter in lower or upper case."""
    out, path = [], []
    def explore(i):
        if i == len(s):
            out.append("".join(path))
            return
        options = sorted({s[i].lower(), s[i].upper()}) if s[i].isalpha() else [s[i]]
        for ch in options:
            path.append(ch)          # choose
            explore(i + 1)           # explore
            path.pop()               # un-choose
    explore(0)
    return out

def combinations_to_target(candidates, target):
    """Every combination that sums to target, using each candidate at most once."""
    candidates = sorted(candidates)
    out, path = [], []
    def explore(start, remaining):
        if remaining == 0:
            out.append(path[:])      # store a copy, not the live list
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue             # the same value at the same level: a duplicate branch
            if candidates[i] > remaining:
                break                # sorted, so nothing later fits either
            path.append(candidates[i])
            explore(i + 1, remaining - candidates[i])
            path.pop()
    explore(0, target)
    return out

Time and space

Backtracking is exponential by nature: there are 2 to the n subsets and n factorial orderings, and copying each answer adds O(n) per answer. Space is O(n) for the recursion and the current path, plus the answers themselves. State the bound honestly, then say what your pruning saves on realistic inputs.

Common mistakes

• Appending path instead of a copy, so every stored answer turns out to be the same final list.
• Forgetting to undo the choice, so later branches start from a dirty state.
• Producing duplicates when the input repeats values; sort, then skip equal neighbors at the same level.
• Checking constraints only at the leaves, which explores far more of the tree than needed.
• Recursing with i where i + 1 is meant, or the reverse, which changes whether an item can be reused.

How to explain it out loud

Describe the decision tree before coding: "At each step I choose which candidate comes next, only from those after the last one I took, so each combination is built once and in order." Then say where you prune and why. What the interviewer wants to hear is that you can see the tree and know which branches you cut.

Give the exponential bound plainly, explain why you store a copy, and trace the first few branches of a three-item example. Narrating the choose, explore, un-choose rhythm while you type is exactly the kind of thinking out loud Devana's rubric scores.