Backtracking with Pruning (Early Feasibility Checks)

Pruning cuts branches that cannot lead to a valid or optimal answer—often using partial sums, remaining capacity, or sorted order monotonicity.

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)

Before recursing, check feasibility: if partial > target: return. Sort input when pruning relies on “smallest remaining can’t catch up”.

Try this in Python

def valid_partition(nums: list[int], k: int, max_sum: int) -> bool:
    if k == 0:
        return True

    def dfs(i: int, cur: int, parts: int) -> bool:
        if parts == k:
            return i == len(nums)
        if cur == max_sum:
            return dfs(i, 0, parts + 1)
        if i == len(nums):
            return False
        if cur + nums[i] <= max_sum:
            if dfs(i + 1, cur + nums[i], parts):
                return True
        return False

    return dfs(0, 0, 0)


print(valid_partition([4, 3, 2, 3, 5, 2, 1], 4, 5))

Common mistakes

• Pruning that is too aggressive—removes valid solutions.
• Integer overflow in partial aggregates.

Key takeaways

• Prove pruning rule with a counterexample hunt.
• Combine with strong ordering of choices to dedupe (e.g., combo sum II).