寻求高效生成满足约束的10元整数组（和为100）的方法

原10层嵌套循环的问题在于遍历了所有可能的组合，计算量达到约2.8×10¹³次，完全不可行。下面推荐分治法，通过拆分问题将计算量降低到约10⁸量级，大幅提升效率。

核心思路 #

把10个元素拆分为前后两组（比如前5个和后5个）：

1. 遍历前5个元素的所有合法组合，记录每个组合的元素和以及对应的组合本身，存入一个字典（键为和，值为该和对应的所有前5元组列表）。
2. 遍历后5个元素的所有合法组合，计算当前组合的和sum_back，则需要前5组的和为100 - sum_back。如果这个目标和存在于字典中，就将对应的前5元组与当前后5元组拼接，得到符合条件的完整10元组。

这种拆分将原本的10维遍历拆分为两个5维遍历，计算量从O(M1*M2*...*M10)降到O(M1*M2*...*M5 + M6*...*M10)，效率提升几个数量级。

代码实现 #

maxs = [3, 9, 14, 21, 21, 35, 31, 49, 42, 38]
combinations = []

# 第一步：预处理前5个元素的所有组合及其和
sum_front_map = {}
for s1 in range(maxs[0]+1):
    for s2 in range(maxs[1]+1):
        for s3 in range(maxs[2]+1):
            for s4 in range(maxs[3]+1):
                for s5 in range(maxs[4]+1):
                    current_sum = s1 + s2 + s3 + s4 + s5
                    # 提前过滤超过100的无效组合
                    if current_sum > 100:
                        continue
                    combo = [s1, s2, s3, s4, s5]
                    if current_sum not in sum_front_map:
                        sum_front_map[current_sum] = []
                    sum_front_map[current_sum].append(combo)

# 第二步：遍历后5个元素，匹配前5组的和
for s6 in range(maxs[5]+1):
    for s7 in range(maxs[6]+1):
        for s8 in range(maxs[7]+1):
            for s9 in range(maxs[8]+1):
                for s10 in range(maxs[9]+1):
                    current_sum = s6 + s7 + s8 + s9 + s10
                    target_sum = 100 - current_sum
                    if target_sum < 0:
                        continue
                    # 查找对应前5组合并拼接
                    if target_sum in sum_front_map:
                        for front_combo in sum_front_map[target_sum]:
                            full_combo = front_combo + [s6, s7, s8, s9, s10]
                            combinations.append(full_combo)

# 验证结果数量
print(f"找到的组合数：{len(combinations)}")

额外优化方案：递归剪枝法 #

如果不想用多层嵌套循环，也可以用递归+剪枝的方式，提前终止无效分支：

maxs = [3, 9, 14, 21, 21, 35, 31, 49, 42, 38]
combinations = []
n = len(maxs)
# 预计算后缀最大和，用于快速剪枝
suffix_max_sum = [0]*n
suffix_max_sum[-1] = maxs[-1]
for i in range(n-2, -1, -1):
    suffix_max_sum[i] = suffix_max_sum[i+1] + maxs[i]

def backtrack(pos, current_sum, path):
    if pos == n:
        if current_sum == 100:
            combinations.append(path.copy())
        return
    # 剪枝：当前和已超100，直接返回
    if current_sum > 100:
        return
    # 剪枝：剩余位置的最大和无法补足差值，直接返回
    needed = 100 - current_sum
    if suffix_max_sum[pos] < needed:
        return
    # 遍历当前位置的所有合法取值
    for num in range(maxs[pos]+1):
        path.append(num)
        backtrack(pos+1, current_sum + num, path)
        path.pop()

backtrack(0, 0, [])
print(f"找到的组合数：{len(combinations)}")

递归剪枝法代码更简洁，适合维度变化的场景，但效率略低于分治法（存在函数调用开销），但相比原方法已经是质的提升。

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