Pruning the search

Pruning means proving early that a partial solution is hopeless and returning immediately instead of exploring everything below it. Cutting one branch near the root can remove millions of nodes.

There are a few kinds. Feasibility pruning stops when a rule is already broken (sum above target, queen attacked). Bound pruning, also called branch and bound, stops when even the best possible completion cannot beat the best answer found so far. Symmetry and duplicate pruning skips branches that are mirror images of ones already tried.

Ordering also matters: trying the most constrained or most promising choice first makes failures and good answers appear early, so more pruning happens later.

1. 1Feasibility check: before recursing, test whether the partial state already violates a rule; if so, skip this choice.
2. 2Sort to enable early breaks: with positive numbers in ascending order, once one value is too large all later ones are too.
3. 3Bound check: compute an optimistic estimate of the best completion (for example current value plus all remaining values); if it cannot beat the best so far, return.
4. 4Duplicate and symmetry skip: if two choices lead to identical subtrees (same value at the same level, two empty buckets), try only one.
5. 5Order choices: try large or highly constrained items first so dead ends are found near the root.
6. 6Memoize failures when the same remaining state can be reached in different ways; at that point the search is turning into dynamic programming.

def can_partition_k(nums, k):
    total = sum(nums)
    if total % k:
        return False                    # prune before searching at all
    target = total // k
    nums = sorted(nums, reverse=True)   # big items first fail fast
    if nums[0] > target:
        return False
    buckets = [0] * k

    def place(i):
        if i == len(nums):
            return True                 # every bucket is exactly target
        seen = set()
        for b in range(k):
            if buckets[b] + nums[i] > target or buckets[b] in seen:
                continue                # overflow, or a twin bucket tried
            seen.add(buckets[b])
            buckets[b] += nums[i]
            if place(i + 1):
                return True
            buckets[b] -= nums[i]
        return False

    return place(0)

Four pruning rules: the divisibility and largest-item checks reject impossible inputs instantly, descending order makes big items fail fast, the overflow check is feasibility pruning, and the seen set skips buckets with the same current sum because they lead to identical subtrees (this also covers empty buckets).

Cost: Pruning rarely changes the worst-case big-O, which stays exponential, but it can reduce the explored nodes by orders of magnitude on real inputs. Each check should be O(1) or close to it.