State-Space Pruning

State pruning removes symmetric or dominated states—e.g., in coin change combinations, always enforce non-decreasing index order to avoid permutations of same multiset.

Why this shows up in the real world

Puzzle games, constraint solvers, and interview combinatorial search all share the same skeleton: build state, recurse, undo.

Core idea (explained for students)

Encode canonical state keys (mask, last, sum) and memoize; drop transitions that revisit dominated (mask, sum) pairs.

Try this in Python

def climb_stairs(n: int) -> int:
    memo: dict[int, int] = {0: 1, 1: 1}

    def ways(k: int) -> int:
        if k in memo:
            return memo[k]
        memo[k] = ways(k - 1) + ways(k - 2)
        return memo[k]

    return ways(n)


print(climb_stairs(5))

Common mistakes

• Canonicalization too weak—still duplicates.
• Memo key missing dimension—wrong reuse.

Key takeaways

• Hash frozen state with frozenset or sorted tuple.
• Compare with brute for n≤8 to validate pruning.