Complexity

The running time of backtracking boils down to nodes visited times work per node. In the worst case it walks the whole state-space tree, so most problems are exponential or factorial. Pruning cannot change that upper bound, but it can drastically shrink the number of nodes actually visited. This chapter lists the complexity of the classic problems, measures the effect of pruning, and compares backtracking with brute force and dynamic programming (DP).

Complexity of the classic problems

The extra factor n or k in the time column is the cost of copying each solution into the output. The space column counts only the recursion depth and path; the output list needs room for every solution on top of that. The best case depends on the problem. A Sudoku solver that needs a single answer can finish in time proportional to the number of blanks if its first guesses are right, but when every solution must be listed, the number of solutions itself is a lower bound.

Measuring the effect of pruning

Count the nodes the N-Queens search actually visits, and compare with placing a queen in any column of each row (n^n) and with only avoiding repeated columns (n!).

def count_nodes(n):
    cols, diag, anti = set(), set(), set()
    visited = 0

    def place(row):
        nonlocal visited
        visited += 1
        if row == n:
            return
        for c in range(n):
            if c in cols or row - c in diag or row + c in anti:
                continue
            cols.add(c); diag.add(row - c); anti.add(row + c)
            place(row + 1)
            cols.remove(c); diag.remove(row - c); anti.remove(row + c)

    place(0)
    return visited

for n in (4, 8, 12):
    print(n, count_nodes(n))

At n = 12 the search visits roughly 0.2% of n! nodes. The bound is the same, but the real amount of work differs by orders of magnitude, and that is what makes backtracking practical.

Cutting deeper with sorting and bounds

When looking for subsets that sum to target, sorting the numbers first means that once a number exceeds the remaining sum, every number after it can be skipped too. The key detail is that you can break instead of continue.

def subset_sum(nums, target):
    nums = sorted(nums)
    result, path = [], []

    def dfs(start, remain):
        if remain == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remain:
                break                 # later numbers are larger: cut them all
            path.append(nums[i])
            dfs(i + 1, remain - nums[i])
            path.pop()

    dfs(0, target)
    return result

print(subset_sum([8, 2, 6, 3, 5], 11))  # [[2, 3, 6], [3, 8], [5, 6]]

Brute force and DP compared

The right tool depends on the question. To list every subset that sums to target, use backtracking. To ask whether one exists or how many there are, DP answers in O(n · target) and is far faster.

def count_subset_sum(nums, target):
    ways = [1] + [0] * target       # ways[s] = number of subsets summing to s
    for x in nums:
        for s in range(target, x - 1, -1):
            ways[s] += ways[s - x]
    return ways[target]

print(count_subset_sum([8, 2, 6, 3, 5], 11))  # 3

Summary

• The upper bound of backtracking is the size of the state-space tree, typically on the order of 2^n or n!.
• Pruning does not change that bound, but it cuts the nodes actually visited by orders of magnitude.
• Use backtracking when every solution must be listed; consider DP first when you only need a count or an optimum and subproblems overlap.