Memoising a Backtracking Search Whose States Repeat

A backtracking search becomes dynamic programming when its calls are identified by a small state that repeats: store the answer for each state, and every repeat is answered from the store. This example memoises a search that counts the sets of dishes costing exactly a budget, and counts the calls it makes with and without the memo.

A group must spend a voucher in full on dishes, each ordered at most once. The search walks the menu in order and, at each dish, either skips it or orders it if it fits. A call is fully described by two numbers: the index of the dish being decided and the budget left. The dishes already ordered do not matter, only what they cost, and that is in the budget left. Two different orders that reach dish 8 with 12 left face exactly the same question: how many ways can dishes 8 onwards make 12? That pair, (index, left), is the state, and the memo is keyed by it.

The listing below holds the plain search and the memoised one, identical except for the highlighted line, and runs both on four menus of growing size.

from functools import cache


def count_plain(prices: list[int], budget: int) -> tuple[int, int]:
    calls = 0

    def ways(index: int, left: int) -> int:
        nonlocal calls
        calls += 1
        if left == 0:
            return 1
        if index == len(prices):
            return 0
        total = ways(index + 1, left)
        if prices[index] <= left:
            total += ways(index + 1, left - prices[index])
        return total

    return ways(0, budget), calls


def count_memoised(prices: list[int], budget: int) -> tuple[int, int]:
    calls = 0

    @cache
    def ways(index: int, left: int) -> int:
        nonlocal calls
        calls += 1
        if left == 0:
            return 1
        if index == len(prices):
            return 0
        total = ways(index + 1, left)
        if prices[index] <= left:
            total += ways(index + 1, left - prices[index])
        return total

    return ways(0, budget), calls


menus = [
    ([4, 6, 7, 9, 11], 17),
    ([4, 6, 7, 9, 11, 3, 5, 8, 10, 12], 30),
    ([4, 6, 7, 9, 11, 3, 5, 8, 10, 12, 2, 6, 7, 9, 4], 45),
    ([4, 6, 7, 9, 11, 3, 5, 8, 10, 12, 2, 6, 7, 9, 4, 5, 8, 3, 11, 6], 60),
]
for prices, budget in menus:
    sets, plain = count_plain(prices, budget)
    same, memo = count_memoised(prices, budget)
    assert sets == same
    print(f"{len(prices)} dishes, budget {budget}: {sets} sets, {plain} calls plain, {memo} calls memoised")

5 dishes, budget 17: 2 sets, 40 calls plain, 36 calls memoised
10 dishes, budget 30: 28 sets, 894 calls plain, 194 calls memoised
15 dishes, budget 45: 809 sets, 26657 calls plain, 486 calls memoised
20 dishes, budget 60: 22310 sets, 831185 calls plain, 897 calls memoised

On the five dishes of Backtracking Example: Choosing Dishes That Fit a Budget Exactly the memo saves almost nothing, 36 calls against 40, because few states repeat in so small a tree. On 20 dishes with a budget of 60 the plain search made 831,185 calls and the memoised one 897. The memoised search can make at most two calls for each state, and there are (20 + 1) × (60 + 1) = 1,281 states, so its work grows with the number of dishes times the budget, while the plain search's grows with 2 to the power of the number of dishes.

The memo changes what the search can return. It counted 22,310 sets without listing one; listing them all would take at least 22,310 steps, memo or not, which is why a problem that asks for every candidate stays a backtracking problem. Asked for a count, a best value or whether any set exists, the memoised search is dynamic programming written top down, the same table Memoisation and Tabulation fills from the bottom up.