Backtracking

Some problems ask for all the solutions: every subset, every permutation, every way to place 8 queens. Backtracking builds a solution one choice at a time; when it has a complete solution it records it, and when a choice is done it undoes it and tries the next.

The template

def backtrack(path, choices):
    if the path is a complete solution:
        record a copy of path
        return
    for choice in the choices still allowed:
        path.append(choice)          # choose
        backtrack(path, ...)         # explore
        path.pop()                   # un-choose

Subsets

At each position, an element is either in or out. Recording the path at every node of the search, and only moving forward through the list, gives each subset exactly once:

def subsets(items):
    result = []
    path = []

    def backtrack(start):
        result.append(path[:])            # every path is a subset
        for i in range(start, len(items)):
            path.append(items[i])         # choose
            backtrack(i + 1)              # explore
            path.pop()                    # un-choose

    backtrack(0)
    return result

print(subsets(["a", "b", "c"]))

Step through and watch path grow and shrink: that shrinking is the "back" in backtracking. n elements give 2ⁿ subsets, so the time is O(n × 2ⁿ): exponential, as any algorithm that lists them all must be. Note path[:]: recording path itself would store the same list, which ends up empty.

Permutations

Every order of n items: at each level, choose any item not used yet. n! of them, so keep n small (8! = 40,320 is fine; 12! is half a billion).

Combination sum, and pruning

All combinations of the numbers that add up to a target, each number usable any number of times.

def combination_sum(candidates, target):
    candidates = sorted(candidates)
    result = []

    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remaining:
                break                     # pruning: every later candidate is bigger too
            path.append(c)
            backtrack(i, path, remaining - c)   # i, not i + 1: c may be used again
            path.pop()

    backtrack(0, [], target)
    return result

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

Two tricks make it work:

• No duplicates: only allow choices from the current position onward, so [2, 3] is found but never [3, 2] as well.
• Pruning: with the candidates sorted, once a candidate is bigger than what is left of the target, every later one is too, so the loop stops (break). Cutting off branches that cannot succeed is what makes backtracking fast enough in practice; the N-queens and Sudoku solvers rely on it.

Mark lesson complete