如何在递归函数中使用for循环获取所有可能的组合？

你的代码存在两个核心问题：

1. 生成了顺序不同的重复组合（比如[5,2,2,1]和[5,2,1,2]被视为不同结果，但题目需要的是不考虑顺序的组合）
2. 部分合法组合（如全2的[2,2,2,2,2]）无法被遍历到，导致结果不完整

修复后的代码 #

combinations = []

def getCombinations(num_types, max_amount, current_combi=None, start_idx=0, current_sum=0):
    if current_combi is None:
        current_combi = []
    # 从start_idx开始遍历，避免生成逆序的重复组合
    for i in range(start_idx, len(num_types)):
        num = num_types[i]
        new_sum = current_sum + num
        if new_sum == max_amount:
            # 添加当前组合的副本，避免引用问题
            combinations.append(current_combi + [num])
        elif new_sum < max_amount:
            # 递归时保持start_idx为当前i，确保后续只能选当前元素及之后的元素
            getCombinations(num_types, max_amount, current_combi + [num], i, new_sum)

getCombinations([5,2,1], 10)
print(combinations)

关键修复点说明 #

• 控制元素选择范围：通过start_idx参数，强制递归时只能从当前元素的索引开始遍历，保证组合中的元素始终按原列表顺序排列（非递增），彻底避免生成不同顺序的重复组合。
• 优化求和逻辑：新增current_sum参数传递当前组合的和，避免每次调用sum(current_combi)带来的性能损耗。
• 避免列表引用问题：使用current_combi + [num]创建新列表传递给递归函数，无需手动修改原列表的元素，代码更简洁且不会出现引用混乱。

输出结果 #

运行后会得到完整的预期组合：

[[5, 5], [5, 2, 2, 1], [5, 2, 1, 1, 1], [5, 1, 1, 1, 1, 1], [2, 2, 2, 2, 2], [2, 2, 2, 1, 1, 1], [2, 2, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

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