Python递归函数未更新参数引发死循环问题求助

死循环原因 #

你的代码陷入死循环的核心问题在difference函数逻辑：

• 当targetdiff >= number时，仅递归调用difference(number, diff)并返回生成器，但未更新当前循环的targetdiff或valid变量。导致while循环一直重复同一判断条件（targetdiff=4和number=3始终不变），永远无法退出。
• 递归生成器的使用方式错误，未展开递归结果，无法推进余数处理流程。

核心逻辑缺陷 #

除死循环外，思路还缺少两个关键部分：

1. 未处理"用完当前大数后，切换到更小的数继续凑剩余目标值"的逻辑，无法生成所有有效组合。
2. 未正确收集输出完整组合列表，仅尝试统计次数，无法得到[3,1]这类具体组合。

修正后的实现方案 #

用回溯法实现，先将数组降序排序以优先使用大数，通过递归尝试当前数的所有可能使用次数，再切换到下一个更小的数处理剩余目标值，确保组合按要求优先输出含大数的结果：

def find_combinations(numbers, target):
    # 降序排序，优先使用大数
    numbers_sorted = sorted(numbers, reverse=True)
    result = []
    
    def backtrack(index, remaining, current_comb):
        if remaining == 0:
            # 找到有效组合，加入结果列表
            result.append(current_comb.copy())
            return
        if index >= len(numbers_sorted):
            return
        
        current_num = numbers_sorted[index]
        # 计算当前数最多能使用的次数
        max_count = remaining // current_num
        
        # 从最多次数到0次尝试（保证优先输出含更多当前大数的组合）
        for count in range(max_count, -1, -1):
            # 添加count个当前数到组合中
            for _ in range(count):
                current_comb.append(current_num)
            # 递归处理下一个更小的数，剩余目标值减去count*current_num
            backtrack(index + 1, remaining - count * current_num, current_comb)
            # 回溯，移除添加的当前数
            for _ in range(count):
                current_comb.pop()
    
    backtrack(0, target, [])
    return result

# 测试调用
combinations = find_combinations([1,2,3], 4)
for comb in combinations:
    print(comb)

代码说明 #

1. 降序排序：确保先处理最大的数，符合"优先选用较大数"的要求。
2. 回溯逻辑：
   • 从当前索引开始，避免生成顺序不同的重复组合（如不会同时出现[3,1]和[1,3]）。
   • 对当前数尝试从最多使用次数到0次，含更多大数的组合会被优先加入结果列表。
   • 递归后回溯，移除当前数，尝试更少次数或切换到更小的数。
3. 结果输出：运行后按要求输出：

   [3, 1]
   [2, 2]
   [2, 1, 1]
   [1, 1, 1, 1]
   

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