Python补全实现all_sums(num, bound)整数和生成器

核心去重逻辑 #

要保证每个数字组合只返回一次，核心是约束选数顺序：每次选择的加数都不小于上一次选中的加数，从根源避免出现数字相同、顺序不同的重复表达式（比如不会同时生成1 + 3和3 + 1）。
所有选中的加数需要同时满足三个约束：

• 是正整数
• 数值不大于传入的bound
• 累加总和恰好等于num

完整实现代码 #

def all_sums(num, bound):
    def helper(remain, min_pick, current_path):
        # 剩余需要凑的和为0，说明当前路径是合法组合
        if remain == 0:
            yield ' + '.join(map(str, current_path))
            return
        # 选数范围：不小于上一次选的数、不超过bound、不超过剩余需要凑的和
        max_pick = min(bound, remain)
        for i in range(min_pick, max_pick + 1):
            yield from helper(remain - i, i, current_path + [i])
    
    # 初始状态：剩余和为num，最小可选正整数为1，初始路径为空
    yield from helper(num, 1, [])

代码验证 #

运行示例输入：

res = all_sums(4, 3)
print(list(res))

输出结果（集合完全匹配要求，顺序仅为遍历逻辑差异，不影响正确性）：

['1 + 1 + 1 + 1', '1 + 1 + 2', '1 + 3', '2 + 2']

原代码问题说明 #

• 预先初始化lst、new列表属于冗余操作，递归过程中直接传递路径参数即可，避免外部状态被污染
• 递归终止条件逻辑错误：原逻辑判断num == 1就追加'1'，没有校验当前已选数字的总和是否匹配目标值，会生成无效结果
• 缺少选数顺序约束：没有限制后续选数的大小范围，会生成数字组合相同、顺序不同的重复表达式
• 递归逻辑不完整：最后一行yield from未完成参数传递，也没有处理选数后的剩余和计算，无法正常递归遍历所有组合

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