Pruning Search Trees (Constraint Propagation)

Constraint propagation prunes whole families of choices at once—e.g., remaining slots cannot fit remaining min values after sorting.

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)

Compute cheap bounds: min_remaining, max_remaining, or prefix feasibility before branching deeply.

Try this in Python

def can_jump(nums: list[int]) -> bool:
    goal = len(nums) - 1
    for i in range(len(nums) - 2, -1, -1):
        if i + nums[i] >= goal:
            goal = i
    return goal == 0


print(can_jump([2, 3, 1, 1, 4]))

Common mistakes

• Bounds that assume sorted input without sorting.
• Double-counting when combining forward and backward feasibility.

Key takeaways

• Precompute prefix sums or suffix max arrays for O(1) checks inside DFS.
• Keep pruning checks pure functions for unit tests.