求将正整数列表划分为K个子集、最小化最大子集和的高效算法

问题定义 #

给定正整数数组nums和整数K，需要将数组划分为K个非空子集，使得所有子集的和中的最大值尽可能小。这等价于任务调度场景：K个工人分配n个任务，每个任务耗时对应数组元素，目标是让单个工人的最长工作时间最短。

比如数组[1,2,3,4,5]、K=2时，最优划分是[1,2,5]和[3,4]，最大子集和为8。

高效解法推荐 #

1. 二分查找 + 回溯剪枝（面试首选）

这是兼顾效率和实现难度的最优方案，核心逻辑是通过二分查找缩小可能的最大子集和范围，再用带剪枝的回溯验证该值是否可行。

思路细节：

• 确定二分边界：
  • 左边界left：数组中的最大值（每个子集至少包含一个元素，所以最大子集和不可能小于最大元素）
  • 右边界right：数组所有元素的总和（对应K=1的极端情况）
• 回溯验证剪枝技巧：
  1. 先将数组从大到小排序，优先处理大元素，能快速排除不可能的情况
  2. 跳过和前一个子集和相同的桶，避免重复计算
  3. 如果当前元素放入某个桶后刚好达到目标值，直接尝试下一个元素（子集无序，放在哪个桶效果一致）

代码实现（Python）：

def can_split(nums, k, target):
    nums.sort(reverse=True)
    buckets = [0] * k

    def backtrack(idx):
        if idx == len(nums):
            return True
        for i in range(k):
            # 剪枝：跳过和前一个桶相同的状态，避免重复计算
            if i > 0 and buckets[i] == buckets[i-1]:
                continue
            # 当前元素放入桶后超过目标，跳过
            if buckets[i] + nums[idx] > target:
                continue
            buckets[i] += nums[idx]
            if backtrack(idx + 1):
                return True
            buckets[i] -= nums[idx]
            # 剪枝：空桶放入元素后失败，后续空桶也不用试了
            if buckets[i] == 0:
                break
        return False

    return backtrack(0)

def min_largest_subset_sum(nums, k):
    left = max(nums)
    right = sum(nums)
    while left < right:
        mid = (left + right) // 2
        if can_split(nums, k, mid):
            right = mid
        else:
            left = mid + 1
    return left

# 测试示例
nums = [1,2,3,4,5]
k = 2
print(min_largest_subset_sum(nums, k))  # 输出8

2. 动态规划（仅适用于小数据量）

当数组长度n较小（比如n≤20）时，可以用动态规划解决，状态记录已选元素的划分状态。

思路细节：

• 用mask（二进制数）表示已选元素的集合，dp[mask]存储该集合划分成K个子集后，各个子集和的有序数组（从小到大）
• 转移时，将新元素加入到某个子集，更新有序数组，记录能得到最小最大和的状态

代码实现（Python）：

def min_largest_subset_sum_dp(nums, k):
    n = len(nums)
    dp = [None] * (1 << n)
    dp[0] = [0] * k

    for mask in range(1, 1 << n):
        # 找到当前新增的元素索引
        idx = (mask & -mask).bit_length() - 1
        prev_mask = mask ^ (1 << idx)
        prev_buckets = dp[prev_mask]
        
        min_max = float('inf')
        best_buckets = None
        # 尝试把当前元素加入每个桶
        for i in range(k):
            new_buckets = prev_buckets.copy()
            new_buckets[i] += nums[idx]
            new_buckets.sort()
            current_max = new_buckets[-1]
            if current_max < min_max:
                min_max = current_max
                best_buckets = new_buckets
        dp[mask] = best_buckets

    return dp[(1 << n) - 1][-1]

# 测试示例
nums = [1,2,3,4,5]
k = 2
print(min_largest_subset_sum_dp(nums, k))  # 输出8

3. 贪心算法（注意：不保证正确性）

贪心思路是每次将最大的元素放入当前和最小的子集，但这种方法存在反例，不能得到通用正确结果，仅在特定场景（如元素大小差异小）下可能有效。

比如反例：[1,1,1,1,2,2]、K=3，贪心会得到最大子集和为4（四个1放入一个桶，两个2各放一个桶），但最优解是将两个2各放一个桶，四个1放一个桶，最大和为2。可见贪心在这里失效。

总结 #

• 面试优先用二分查找+回溯剪枝，效率高、易实现，能处理绝大多数常见输入规模
• 动态规划仅适合小数据量场景，时间复杂度O(n*2^n)，n较大时不可用
• 贪心算法不通用，仅能作为补充思路，无法保证正确解

内容的提问来源于stack exchange，提问作者maplemaple