Backtracking

Backtracking builds answers one choice at a time. When a partial answer can't possibly work, it undoes the last choice and tries the next one. It's how you list every subset, permutation or valid arrangement, like placing queens on a board or filling in a sudoku.

Every backtracking function has the same shape: if the current state is a complete answer, save it. Otherwise, for each possible next choice, make it, recurse, then undo it. The undo step is what makes it backtracking.

Here's finding every combination of numbers that adds up to a target, using each number once, with no duplicate combinations even if the input has repeats:

def subsets_summing_to(numbers, target):
    numbers = sorted(numbers)
    results, chosen = [], []

    def explore(start, remaining):
        if remaining == 0:
            results.append(chosen[:])
            return
        for i in range(start, len(numbers)):
            if i > start and numbers[i] == numbers[i - 1]:
                continue  # Same value, same subtrees. Skip it.
            if numbers[i] > remaining:
                break  # Sorted, so everything after is too big too.
            chosen.append(numbers[i])
            explore(i + 1, remaining - numbers[i])
            chosen.pop()

    explore(0, target)
    return results

For [10, 1, 2, 7, 6, 1, 5] and a target of 8, that returns [1, 1, 6], [1, 2, 5], [1, 7] and [2, 6]. Sorting first is what makes both the duplicate skip and the early stop work.

• Look for "all possible", "every combination" or "generate".
• Say what a choice is, what makes an answer complete, and when you can stop early.
• Give the complexity as roughly the number of answers times the work to build each one.

Finding a word in a grid

Given a grid of letters and a word, check whether the word can be spelled by moving up, down, left or right, without using the same cell twice.

1. Try starting from every cell. From each start, explore(row, column, i) checks whether the word's letters from position i onward can be spelled starting at that cell.
2. If the cell is off the grid, already used, or doesn't match word[i], stop. That's the early cut that keeps it fast.
3. If i is the last letter, you've found the word.
4. Otherwise mark the cell as used, try all four neighbors with i + 1, then unmark it. Unmarking is the backtrack: other paths might need that cell.
5. For 'SEE' in a grid with S, E, E in a line, it goes S, then E, then the second E, and returns True on the third letter.
6. It's O(cells × 4^L) in the worst case for a word of length L, but in practice the letter check cuts off most paths almost immediately.
7. A cheap first check helps: if the grid has fewer of some letter than the word needs, return False without searching.

Things interviewers tend to ask once you've brought this up.

How do you search for many words at once?

Put the words in a trie and walk the grid and the trie together. A path stops as soon as no word starts with those letters.

How do you generate all valid bracket strings with n pairs?

Add '(' while you've used fewer than n, and add ')' while there are more opens than closes. Every path that reaches length 2n is valid.

How would you solve n-queens?

Place one queen per row. Keep sets of used columns and both diagonals, and skip any square that clashes.

Why copy the current list when saving an answer?

Because you keep changing the same list as you backtrack. Without a copy, every saved answer would end up pointing at the same, final list.

• Forgetting to undo a choice, so it leaks into other paths.
• Saving a reference to the working list instead of a copy.
• Not stopping early on paths that can't work.
• Producing duplicate answers when the input has repeats.
• Using backtracking when only a count or best value is needed.

• Dynamic programmingSolve each subproblem once and reuse the answer.
• Trees and recursionSolve tree problems by deciding what each node returns.
• Graph traversal and shortest pathsBFS, DFS and Dijkstra, and when to use each.