Subset Partitioning and k-Way Load Balancing

Partition into k subsets minimizing max sum—binary search on answer with greedy feasibility check is classic; pure DP is exponential in k.

Why this shows up in the real world

Load balancing servers. Paint buckets equalization.

Core idea (explained for students)

For small n,k use DP over masks assigning group id; for large use heuristics or BS+greedy.

Try this in Python

def can_partition_k(nums: list[int], k: int, limit: int) -> bool:
    nums = sorted(nums, reverse=True)

    def dfs(i: int, sums: list[int]) -> bool:
        if i == len(nums):
            return True
        x = nums[i]
        seen = set()
        for j in range(k):
            if sums[j] + x <= limit and sums[j] not in seen:
                sums[j] += x
                seen.add(sums[j] - x)
                if dfs(i + 1, sums):
                    return True
                sums[j] -= x
                if sums[j] == 0:
                    break
        return False

    return dfs(0, [0] * k)


print(can_partition_k([4, 3, 2, 3, 5, 2, 1], 3, 7))

Common mistakes

• Greedy feasibility checker that is not monotone—binary search invalid.
• Off-by-one on k groups.

Key takeaways

• Prove monotonicity of feasible(λ) for search-on-answer.