Backtracking

Subsets, permutations, combinations and constraint search.

Backtracking explores every candidate solution by building it one choice at a time, and undoing each choice after exploring it. It's the pattern for "generate all…" questions and for constraint searches like Sudoku or N-Queens.

When to use it

"Return all subsets / permutations / combinations / partitions"
Search problems with constraints: N-Queens, Sudoku, word search
Small input sizes (n ≤ ~15–20) — the output itself is exponential

The template

def backtrack(path, choices):
    if is_complete(path):
        results.append(path[:])     # copy! path keeps changing
        return
    for choice in choices:
        if not is_valid(choice, path):
            continue                # prune
        path.append(choice)         # choose
        backtrack(path, next_choices(choice))
        path.pop()                  # un-choose

Three questions define every backtracking solution: what is a choice, when is a path complete, and what can be pruned.

Subsets

def subsets(nums):
    results = []
    def dfs(start, path):
        results.append(path[:])              # every node is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1, path)
            path.pop()
    dfs(0, [])
    return results

Permutations

def permutations(nums):
    results, used = [], [False] * len(nums)
    def dfs(path):
        if len(path) == len(nums):
            results.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            dfs(path)
            path.pop()
            used[i] = False
    dfs([])
    return results

Handling duplicates

Sort the input, then skip an element equal to its predecessor at the same depth:

for i in range(start, len(nums)):
    if i > start and nums[i] == nums[i - 1]:
        continue

Pruning

Pruning is what makes backtracking fast enough. Examples: stop when a running sum exceeds the target (with sorted candidates you can break, not just continue); in word search, stop when the prefix isn't in a trie; in N-Queens, track used columns and diagonals in sets.

Complexity

Proportional to the size of the output times the cost to build each item: O(2ⁿ · n) for subsets, O(n! · n) for permutations. State it as output-sensitive.

[!TIP] Practice Generate Subsets and Permutations · Word Search II