Algorithms · Lesson 5 of 6

Backtracking

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

Advanced
16 min read
3 objectives

Before this lessonLesson 4: Greedy Algorithms

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.

Try, and undo if it does not work

Backtracking is how you would solve a maze: walk down a path; if you hit a dead end, step back to the last junction and try another turn. In code it means building a solution one choice at a time, exploring where it leads, and undoing the choice to try the next option. It systematically explores all possibilities while abandoning hopeless branches early. Puzzles such as Sudoku, N-Queens, generating subsets and permutations are all solved this way.

Every backtracking solution follows the same three-beat rhythm: choose an option, explore further with it, unchoose it.

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.

Subsets

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.

Permutations

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.

Generating every subset

def subsets(items):
    result, current = [], []

    def explore(start):
        result.append(current[:])          # record what we have so far
        for i in range(start, len(items)):
            current.append(items[i])       # choose
            explore(i + 1)                 # explore
            current.pop()                  # unchoose

    explore(0)
    return result

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

Output

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

Generating permutations

def permutations(items):
    result, current, used = [], [], [False] * len(items)

    def explore():
        if len(current) == len(items):
            result.append(current[:])
            return
        for i, x in enumerate(items):
            if used[i]:
                continue
            used[i] = True; current.append(x)      # choose
            explore()                              # explore
            current.pop(); used[i] = False         # unchoose

    explore()
    return result

print(permutations(["A", "B", "C"]))

Output

[['A', 'B', 'C'], ['A', 'C', 'B'], ['B', 'A', 'C'], ['B', 'C', 'A'], ['C', 'A', 'B'], ['C', 'B', 'A']]

Pruning: stop bad branches early

Backtracking checks constraints as it goes and abandons a branch the instant it cannot succeed. Here we find combinations that add up to a target, cutting off any branch that already exceeds it.

def combos(nums, target):
    nums.sort()
    out, cur = [], []

    def go(start, remaining):
        if remaining == 0:
            out.append(cur[:]); return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break                        # prune: too big, and all later ones are bigger
            cur.append(nums[i])
            go(i, remaining - nums[i])           # can reuse the same number
            cur.pop()

    go(0, target)
    return out

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

Output

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

Key takeaways

Backtracking = choose, explore, unchoose; it tries every possibility systematically.
Copy the current path when saving a result (current[:]).
Prune branches as early as possible; otherwise the cost explodes exponentially.

# Write your solution here

Up next · Lesson 6Dynamic ProgrammingOverlapping subproblems, memoization, tabulation, knapsack and edit distance.