Forgetting to Undo the Choice

A backtracking function that appends a choice to its shared path and never removes it produces wrong answers, because every branch after the first inherits items an earlier branch left behind. This card shows the symptom, the cause and the one-line fix.

The symptom is output of the right length with the wrong contents: the right number of subsets or orderings, but too long, repeated, or with items appearing twice. Nothing crashes and nothing loops forever, because the recursion still stops when it has decided every item.

def subsets_without_pop(items: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []

    def search(i: int) -> None:
        if i == len(items):
            result.append(list(path))
            return
        path.append(items[i])
        search(i + 1)
        search(i + 1)

    search(0)
    return result


def subsets(items: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []

    def search(i: int) -> None:
        if i == len(items):
            result.append(list(path))
            return
        path.append(items[i])
        search(i + 1)
        path.pop()
        search(i + 1)

    search(0)
    return result


print("without pop:", subsets_without_pop([1, 2, 3]))
print("with pop:   ", subsets([1, 2, 3]))

without pop: [[1, 2, 3], [1, 2, 3], [1, 2, 3, 3], [1, 2, 3, 3], [1, 2, 3, 3, 2, 3], [1, 2, 3, 3, 2, 3], [1, 2, 3, 3, 2, 3, 3], [1, 2, 3, 3, 2, 3, 3]]
with pop:    [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

The trigger is lines 10 and 11, where the first function appends an item, searches with it, and then searches again without removing it. The second search is meant to explore the branch that skips the item, but the item is still on the path. The run shows the damage: the first function produced eight lists, as many as there are subsets of three items, but the first two are both [1, 2, 3], no empty subset appears, and the last two hold 3 four times.

The mechanism is that the path is one list shared by every call, not a copy per call. A beginner's model of recursion, where each call has its own list, predicts the right subsets; it is wrong because only the list's reference is shared between calls. Each forgotten append stays in the list for every call that runs afterwards, so the paths keep growing: the last list holds seven items, from three decisions.

The cost is silent wrong output, which a test on one item would miss, since with one item the first branch is the only branch that can go wrong. The remedy is line 27: path.pop() after the search that took the item, before the search that skips it. Choose, explore and unchoose must come as a set, and the second function, with the pop, printed the eight correct subsets.