Pruning backtracking in Python

Why this matters

Backtracking tries a choice, goes deeper, and undoes the choice when it leads nowhere. A plain backtracking search keeps going down every path until the path ends. Many paths end in failure long before the last step. If the search can see that early, it can stop and try something else. That stop is called pruning, after the way a gardener cuts off a branch from a tree.

The recursion tree from the earlier lesson on recursion trees shows every call as a node. Pruning removes whole subtrees from that picture. A subtree is a call and every call below it. A subtree that is cut off is a dead branch: no choice made from there can produce a valid answer.

This lesson shows three searches. In each one you will write the plain version, add a rule that cuts dead branches, and count the calls to see how much work the rule removed. The base case and the call stack are covered in the first lesson of this module, so this lesson assumes you can write a recursive function with a base case.

The idea: a branch that cannot work

Start with a small problem. You have the numbers 2, 3, 5, 7, 8 and 10. You want to pick some of them so they add up to exactly 15.

Suppose you first pick 10. You now need 5 more. The numbers you can still pick are 2, 3, 5, 7, 8 and 10 minus the one you took. If you then pick 8, you need -3 more. You cannot reach 15 by adding positive numbers to a total that is already past it. Every choice after 8 is wasted work. The branch "10 then 8" is dead, and the search can cut it off the moment the remaining amount goes below zero.

The same idea works in the other direction too. Suppose the list is sorted from small to big and you need 5 more. The next number in the list is 7. Since 7 is bigger than 5, and every number after 7 is also bigger than 5, no choice from here can finish the subset. The search can stop the loop right there.

A cut like this does not change the answer. It only skips work that could not have produced an answer. That is the rule for every pruning rule in this lesson: the answers before and after the cut must be the same. You check that by running both versions on the same input.

Example 1: subset sum with a sorted list

The problem: given numbers and a target, list every group of numbers that adds up to the target. Each number can be used at most once.

The plain version

The plain version makes a yes-or-no decision for each number. It either takes the number or skips it. At the end, if the total is exactly the target, it saves the group. With 6 numbers there are 2 to the power 6 paths, which is 64 paths, and every path is visited.

The list chosen holds the numbers picked so far. The method append puts a number at the end of the list, and pop takes the last number off again. That pair is the undo step: after the first recursive call returns, the list goes back to the way it was, so the second call starts clean. The counter calls is a global variable, and the function uses global calls to change it.

The pruned version

The pruned version sorts the numbers first, from small to big. It uses a loop instead of take-or-skip. The loop tries each number from start onward. When a number is bigger than what is still needed, the loop stops, because all the numbers after it are bigger too.

Measuring the saving

To measure, the program counts calls. Each call to either function adds one to calls. A call does a small, fixed amount of work, so the number of calls is a fair measure of the work done. The program runs both versions on the same input and checks that the answers match.

Python · editable

calls = 0

def every_subset(nums: list[int], i: int, remaining: int, chosen: list[int], out: list[list[int]]) -> None:
    # Baseline: decide take or skip for every number. Visits all 2^n paths.
    global calls
    calls += 1
    if i == len(nums):
        if remaining == 0:
            out.append(chosen[:])
        return
    chosen.append(nums[i])
    every_subset(nums, i + 1, remaining - nums[i], chosen, out)
    chosen.pop()
    every_subset(nums, i + 1, remaining, chosen, out)

def pruned(nums: list[int], start: int, remaining: int, chosen: list[int], out: list[list[int]]) -> None:
    # Pruned: the list is sorted ascending. If nums[i] is too big,
    # every later number is too big too, so the loop stops.
    global calls
    calls += 1
    if remaining == 0:
        out.append(chosen[:])
        return
    for i in range(start, len(nums)):
        if nums[i] > remaining:
            break
        chosen.append(nums[i])
        pruned(nums, i + 1, remaining - nums[i], chosen, out)
        chosen.pop()

def run(label: str, nums: list[int], target: int) -> None:
    global calls
    a: list[list[int]] = []
    calls = 0
    every_subset(nums, 0, target, [], a)
    baseline = calls

b: list[list[int]] = []
    calls = 0
    pruned(nums, 0, target, [], b)
    pruned_calls = calls

print(f"{label}: target {target}, {len(nums)} numbers")
    print(f"  baseline calls: {baseline}, answers: {len(a)}")
    print(f"  pruned calls:   {pruned_calls}, answers: {len(b)}")
    print(f"  same answers:   {a == b}")
    print(f"  first answers:  {b[:3]}")

run("small", [2, 3, 5, 7, 8, 10], 15)
run("larger", [2, 3, 5, 7, 8, 10, 12, 15, 18, 20, 23, 25, 30, 35, 40, 45], 60)

Press Run. The output is:

small: target 15, 6 numbers
  baseline calls: 127, answers: 5
  pruned calls:   27, answers: 5
  same answers:   True
  first answers:  [[2, 3, 10], [2, 5, 8], [3, 5, 7]]
larger: target 60, 16 numbers
  baseline calls: 131071, answers: 137
  pruned calls:   1612, answers: 137
  same answers:   True
  first answers:  [[2, 3, 5, 7, 8, 10, 25], [2, 3, 5, 7, 8, 12, 23], [2, 3, 5, 7, 8, 15, 20]]

Read the numbers carefully. For the small input, the pruned version makes 27 calls where the plain version makes 127. That removes 1 minus 27 divided by 127, which is about 78.7 percent of the calls. For the larger input, the pruned version makes 1,612 calls where the plain version makes 131,071. That removes about 98.8 percent of the calls, and both versions find the same 137 answers.

The saving grows with the size of the input because the plain version doubles its work with every extra number, while the pruned version only visits branches where the sum still fits.

Example 2: no two equal letters side by side

The second problem has a rule about neighbours. You have three copies each of the letters a, b and c, and you want every arrangement of the six letters where no two letters that touch are the same. The string aabbcc is not allowed, because the two a's touch. The string abcabc is allowed.

This problem is a good test of pruning because the rule is local. You only need to look at the last letter placed to decide whether a new letter is allowed.

The plain version and the pruned version

The function below places one letter at a time. The list counts says how many copies of each letter are still unused. The flag prune decides whether the function checks the last letter before it places a new one.

The plain version does not look at neighbours while it builds. It builds all 90 arrangements of the six letters, and only at the end does it throw away the ones with two equal letters side by side. That is 271 calls.

The pruned version checks the last letter before it places a new one. If the new letter matches the last letter, that branch is dead, because the two letters now touch and no later letter can separate them. The continue skips that one letter and moves on to the next. Every string the pruned version builds is valid, so it does not need a final check.

Python · editable

LETTERS = ["a", "b", "c"]
calls = 0

def build(counts: list[int], chars: list[str], total: int, prune: bool, out: list[str]) -> None:
    # counts[k] is how many copies of LETTERS[k] are still unused.
    global calls
    calls += 1
    if len(chars) == total:
        out.append("".join(chars))
        return
    for k in range(len(LETTERS)):
        if counts[k] == 0:
            continue
        same_as_last = len(chars) > 0 and chars[-1] == LETTERS[k]
        if prune and same_as_last:
            continue  # this branch can never become a valid string
        counts[k] -= 1
        chars.append(LETTERS[k])
        build(counts, chars, total, prune, out)
        chars.pop()
        counts[k] += 1

def has_adjacent_equal(s: str) -> bool:
    return any(s[i] == s[i - 1] for i in range(1, len(s)))

all_strings: list[str] = []
calls = 0
build([2, 2, 2], [], 6, False, all_strings)
valid = [s for s in all_strings if not has_adjacent_equal(s)]
print("baseline calls:", calls, "strings built:", len(all_strings))
print("baseline valid:", len(valid))

pruned_strings: list[str] = []
calls = 0
build([2, 2, 2], [], 6, True, pruned_strings)
print("pruned calls:  ", calls, "valid:", len(pruned_strings))
print("same answers:  ", valid == pruned_strings)
print("first five:    ", pruned_strings[:5])

The output is:

baseline calls: 271 strings built: 90
baseline valid: 30
pruned calls:   112 valid: 30
same answers:   True
first five:     ['abacbc', 'abcabc', 'abcacb', 'abcbac', 'abcbca']

The pruned version makes 112 calls instead of 271. That removes about 58.7 percent of the calls, and both versions find the same 30 valid strings.

This example has a smaller saving than the first one, and that is normal. The size of the saving depends on how often a dead branch appears early. Here a dead branch is cut as soon as it appears, but many branches are still valid, so most of the work is real work.

Example 3: branch and bound on a knapsack

The third problem is harder, because the search is not looking for a set of answers. It is looking for the single best answer. You have 20 items. Each item has a value and a weight. You may pick any set of items whose total weight is at most 60. You want the set with the biggest total value.

This is the 0/1 knapsack problem. The name comes from packing a bag, where each item is either in the bag or not. The plain search tries every set of items, which is 2 to the power 20, or about one million sets. Pruning can do much better, using a method called branch and bound. The branch is the choice you are making. The bound is a quick estimate of the most value that a branch could still reach.

The bound

Keep the best value found so far in a variable called best. At any point in the search, add up the value of all items you still have not decided on. If the value you already hold plus that remaining total is no bigger than best, then even taking every remaining item cannot beat best. The branch is dead, so the search stops there.

The items in this program come from a formula, so the run is the same every time. The first three items are: item 0 has value 5 and weight 3, item 1 has value 19 and weight 18, and item 2 has value 10 and weight 14.

Python · editable

n = 20
value = [(i * 37) % 23 + 5 for i in range(n)]
weight = [(i * 53) % 19 + 3 for i in range(n)]
capacity = 60

# suffix[i] = total value of items i..n-1, used for the bound.
suffix = [0] * (n + 1)
for i in range(n - 1, -1, -1):
    suffix[i] = suffix[i + 1] + value[i]

best = 0
calls = 0

def search(i: int, weight_so_far: int, value_so_far: int, use_bound: bool) -> None:
    global calls, best
    calls += 1
    if value_so_far > best:
        best = value_so_far
    if i == n:
        return
    if use_bound and value_so_far + suffix[i] <= best:
        # Even taking every remaining item cannot beat the best answer.
        return
    if weight_so_far + weight[i] <= capacity:
        search(i + 1, weight_so_far + weight[i], value_so_far + value[i], use_bound)
    search(i + 1, weight_so_far, value_so_far, use_bound)

print("items:", n, "capacity:", capacity)
best = 0
calls = 0
search(0, 0, 0, False)
print(f"no bound:   best value {best}, calls {calls}")

best = 0
calls = 0
search(0, 0, 0, True)
print(f"with bound: best value {best}, calls {calls}")

The list suffix is built once at the start. suffix[i] holds the total value of items from i to the end, so the bound check is one addition and one comparison. Without this list the program would add up the remaining values again at every call.

The bound check runs before the search tries either choice for item i. That order matters: the cut should happen before any of the work for that branch is done.

The output is:

items: 20 capacity: 60
no bound:   best value 173, calls 80589
with bound: best value 173, calls 13860

Both versions find the best value 173. The plain search makes 80,589 calls. The bounded search makes 13,860 calls, which removes about 82.8 percent of the calls. The bound never cuts a branch that could beat best, so the result is the same on every input.

The bound used here is weak. It adds up values and ignores weights, so it often says a branch could still do better when it cannot. A tighter bound would cut more. This lesson does not measure a tighter bound, so treat it as an idea to try, not a result.

Common mistakes

Storing the list instead of a copy

The lists chosen and out are passed by reference. If you save chosen directly, every saved answer points to the same list. Backtracking keeps changing that list, so at the end the saved answers look empty. Here is a version that saves the list without copying it:

Python · editable

The output is [[], []]. Both answers are empty, even though the answers should be [2, 3] and [5]. The fix is to save a copy: out.append(chosen[:]).

Using break where continue was meant

break leaves the whole loop. continue skips only the current item and moves on. The next program is a short version of the no-adjacent search, with break in place of continue:

Python · editable

The output is leaves: 0. The program finds no valid string at all. When the first letter in the loop matches the last letter, break ends the loop, so the letters after it are never tried. The correct word is continue.

Breaking early on an unsorted list

The break in the subset sum search is only safe because the numbers are sorted. On an unsorted list a big number can come first and stop the loop before the small numbers that follow it are tried. The next program runs the same search on the list 20, 3, 5 with target 8. It repeats the two functions from Example 1, so that the program runs on its own:

Python · editable

The output is all: [[3, 5]] pruned: []. The answer 3 and 5 is missed, because the first number, 20, is bigger than 8 and the loop stops at once. The fix is to sort the list before the search, or to use continue in place of break. continue is safe on any order, but it cuts less work.

Forgetting to undo a choice

Every append in the search needs a matching undo: pop for a list, or counts[k] += 1 for the letter counts. If the undo is missing, the list keeps the number from the earlier branch. Later answers then contain numbers that were never picked on their own path. The bug does not crash the program. It only gives wrong answers, so check the answers on a small input you can work out by hand.

Missing punctuation

A syntax error stops the program before it runs. Python reports it with the file name and line number. For example, if (n > 3: with the closing parenthesis missing gives this output:

  File "typo.py", line 2
    if (n > 3:
             ^
SyntaxError: invalid syntax

The caret points at the place where the parenthesis should be. Put the ) there and run the program again. The file name in your output depends on what you named the file.

Practice

Exercise 1

Run the pruned subset sum function on the sorted list [1, 2, 4, 8] with target 8. How many calls does it make, and which answers does it return?

Show the answer

The pruned function makes 9 calls. It returns one answer, [[8]]. No other group of 1, 2 and 4 adds up to 8.

Exercise 2

Why does the pruned subset sum function give the wrong answer for the list [20, 3, 5] with target 8?

Show the answer

The list is not sorted. The first number, 20, is bigger than 8, so the break stops the loop before it reaches 3 and 5. The answer [3, 5] is never tried. Sorting the list first fixes it.

Exercise 3

Use the no-adjacent-letters rule. How many arrangements of the letters a a a b have no two equal letters side by side?

Show the answer

There are 0. Three a's need at least two other letters between them, to keep them apart. There is only one b, so no arrangement works.

Exercise 4

In the bound check of the knapsack search, change <= to <. That means a branch is cut only when it is strictly worse than the best value, not when it ties. Predict whether the best value changes, and whether the number of calls goes up or down. Then run it.

Show the answer

The best value stays at 173. The number of calls goes up from 13,860 to 14,297. A branch that can only tie the best value is no longer cut, so the search does a little more work. A tie cannot give a better answer, so the answer is still correct.

Exercise 5

Add a line to the subset sum program that prints the number of answers returned by pruned for the list [2, 3, 5, 7, 8, 10] with target 15. What number should it print?

Show the answer

It prints 5. The answers are [2, 3, 10], [2, 5, 8], [3, 5, 7], [5, 10] and [7, 8]. The first three match the output shown earlier. The last two are the groups that also add up to 15.

Summary

Pruning cuts a branch of the search when no choice from that point can give a valid answer.
A break in a sorted loop can stop a whole range of choices at once, but it is only safe when the order is known.
Branch and bound stops a branch when even the best possible rest cannot beat the best answer found so far.
Measure pruning by counting calls on the same input, and check that the answers are the same as the plain version.
Save a copy of the current list with chosen[:] and undo every change before the function returns.

Pruning backtracking in Python

Why this matters

The idea: a branch that cannot work

Example 1: subset sum with a sorted list

The plain version

The pruned version

Measuring the saving

Example 2: no two equal letters side by side

The plain version and the pruned version

Example 3: branch and bound on a knapsack

The bound

Common mistakes

Storing the list instead of a copy

Using break where continue was meant

Breaking early on an unsorted list

Forgetting to undo a choice

Missing punctuation

Practice

Exercise 1

Exercise 2

Exercise 3

Exercise 4

Exercise 5

Summary

Stuck? Ask the tutor