如何高效将整数列表拆分为两个和差最小的整数组？

你的原始方法效率极低的核心原因是生成了所有排列，但实际上我们只需要考虑元素的分组（子集），不需要关心组内元素的顺序，也不需要重复计算互补的分组（比如把A放第一组和放第二组本质是同一个差值）。这个问题本质是经典的划分问题（Partition Problem），属于NP-hard，但针对小规模输入（比如你的8个元素），可以用非常高效的方法解决。

方法一：枚举所有可能的子集（针对小规模输入） #

我们只需要枚举所有非空且不包含全部元素的子集，计算每个子集的和与总和的一半的差值，记录最小差值对应的分组。由于每个子集和它的补集是同一对分组，我们只需要枚举一半的子集即可。

代码实现：

lengths = [240, 255, 270, 240, 220, 230, 420, 470]
total = sum(lengths)
min_diff = float('inf')
best_split = None

# 枚举所有非空真子集，跳过重复的互补分组
for mask in range(1, 1 << len(lengths)):
    complement_mask = (~mask) & ((1 << len(lengths)) - 1)
    if mask > complement_mask:
        continue
    
    subset = []
    complement = []
    for i in range(len(lengths)):
        if mask & (1 << i):
            subset.append(lengths[i])
        else:
            complement.append(lengths[i])
    
    current_diff = abs(sum(subset) - sum(complement))
    if current_diff < min_diff:
        min_diff = current_diff
        best_split = (tuple(subset), tuple(complement))
        if min_diff == 0:
            break  # 差值为0已是最优，直接退出

print(best_split, min_diff)

这个方法的迭代次数仅127次（2^8/2 -1），相比你的282240次，效率提升了2000多倍，运行后会得到与你结果等价的最优分组（差值均为5）。

方法二：动态规划（针对较大规模输入） #

如果元素数量增加（比如20个以上），枚举子集的方法会变慢，此时可以用动态规划，目标是找到最接近总和一半的子集和。

代码实现：

lengths = [240, 255, 270, 240, 220, 230, 420, 470]
total = sum(lengths)
target = total // 2

# dp[i]表示是否能组成和为i的子集
dp = [False] * (target + 1)
dp[0] = True

for num in lengths:
    # 逆序遍历避免重复使用同一个元素
    for i in range(target, num - 1, -1):
        if dp[i - num]:
            dp[i] = True

# 找到最大的可达成子集和
max_subset_sum = max(i for i, val in enumerate(dp) if val)
min_diff = total - 2 * max_subset_sum

# 回溯找到对应的子集
subset = []
remaining = max_subset_sum
for num in reversed(lengths):
    if remaining >= num and dp[remaining - num]:
        subset.append(num)
        remaining -= num

# 生成补集
temp_subset = subset.copy()
complement = []
for num in lengths:
    if num in temp_subset:
        temp_subset.remove(num)
    else:
        complement.append(num)

print(tuple(subset), tuple(complement), min_diff)

这个方法的时间复杂度为O(ntarget)，其中n是元素数量，target是总和的一半。针对你的输入，计算量仅81172=9376次，远优于原始方法，且能处理更大规模的输入。

原始方法低效的根源 #

原始方法中，permutations(lengths)生成了8!=40320种排列，每种排列又拆分7次，共282240次计算，但绝大多数都是重复的分组——不同排列拆分出的分组本质是同一个子集，却被重复计算了多次。

内容的提问来源于stack exchange，提问作者Ξένη Γήινος