Advanced 16 min

Backtracking

Explore choices, undo them, and generate permutations and subsets.

What you will learn

Use choose-explore-unchoose
Generate subsets and permutations
Prune the search

Backtracking is systematic trial and error. You build a solution one choice at a time; if a partial solution cannot possibly work, you undo the last choice and try another. It is the tool for problems that ask for all arrangements: subsets, permutations, puzzles like Sudoku and N-Queens.

The pattern: choose, explore, unchoose

Every backtracking solution has the same skeleton: if the current path is a complete answer, record it; otherwise, for each available option, add it to the path, recurse, then remove it again.

def subsets(nums):
    result, path = [], []

    def go(start):
        result.append(path[:])            # every path is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])         # choose
            go(i + 1)                    # explore
            path.pop()                   # unchoose

    go(0)
    return result

print(subsets([1, 2, 3]))

Output

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Note path[:]: append a copy, because path keeps changing afterward. Forgetting the copy is the most common bug.

def permutations(nums):
    result, path, used = [], [], [False] * len(nums)

    def go():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True; path.append(nums[i])
            go()
            path.pop(); used[i] = False

    go()
    return result

print(permutations([1, 2, 3]))

Output

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Pruning

Pruning means abandoning a branch as soon as you know it is doomed. It is what separates a usable backtracking solution from brute force. Example: combinations that add up to a target. If the running sum already exceeds the target, stop.

def combination_sum(candidates, target):
    candidates.sort()
    result, path = [], []

    def go(start, remaining):
        if remaining == 0:
            result.append(path[:]); return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                    # prune: sorted, so the rest are too big
            path.append(candidates[i])
            go(i, remaining - candidates[i])   # same number may repeat
            path.pop()

    go(0, target)
    return result

print(combination_sum([2, 3, 6, 7], 7))

Output

[[2, 2, 3], [7]]

Cost

Backtracking is exponential in the worst case: 2 to the n subsets, n factorial permutations. That is acceptable for n up to roughly 10 to 20, which is exactly the range these puzzle problems use. If you find repeated subproblems, switch to dynamic programming.

Try it yourself

Generate all valid combinations of n pairs of parentheses. For n=3 there are 5, such as ((())) and ()()(). Prune: only add ( while opens < n, and ) while closes < opens.

Show solution

def gen_parens(n):
    out = []
    def go(cur, opens, closes):
        if len(cur) == 2 * n:
            out.append(cur); return
        if opens < n:
            go(cur + "(", opens + 1, closes)
        if closes < opens:
            go(cur + ")", opens, closes + 1)
    go("", 0, 0)
    return out

print(gen_parens(3))