Python递归求解找零问题时while循环意外删除列表多余元素

你的目标是用递归+回溯的方式求指定金额的所有硬币组合，当前遇到的核心问题是回溯阶段删除列表元素的逻辑不符合预期，出现了“多删”的现象，本质是对递归调用栈的层级执行逻辑理解不到位，同时回溯逻辑的设计有错误。

1. 多余的删数操作来自上一层递归的回溯
   你看到的额外输出的[1, 1, 1]和Done!不是当前层代码的执行结果，而是上一层递归调用在子递归执行完成后，运行自身的回溯逻辑产生的输出。你当前的代码每一层递归调用，在处理完当前硬币的所有子分支后，都会执行一次while判断和del lst[-1]，多层递归的回溯逻辑会依次执行，就出现了你以为的“多删”现象。
2. 回溯逻辑设计错误
   你预期的逻辑是“末尾是最大值删两个，否则删一个”，但现有代码的while循环会删除所有连续在末尾的最大值硬币，再额外删一个，完全不符合标准回溯的逻辑：你每轮循环只向列表追加了1个硬币，处理完所有子情况后，只需要删除你刚才追加的这1个硬币即可，不需要额外删除其他元素。
3. 重复组合问题
   你每次递归都传入完整的硬币元组，会生成大量重复的排列式组合，比如[1,3]和[3,1]，二者是同一种找零组合，不需要重复统计。

1. 去掉多余的while循环，回溯阶段只删除当前轮次追加的1个硬币即可。
2. 递归时传入从当前硬币开始的子序列，避免生成重复的排列组合。
3. 避免使用全局变量存储中间结果和最终结果，降低代码耦合度。

def make_change(amount, coins):
    result = []
    # 按从小到大排序硬币，方便后续去重和剪枝
    coins = sorted(coins)
    def backtrack(remaining, path, start):
        if remaining == 0:
            result.append(path.copy())
            return
        if remaining < 0:
            return
        # 从start开始遍历，避免生成重复的排列组合
        for i in range(start, len(coins)):
            coin = coins[i]
            # 剪枝：如果当前硬币已经大于剩余金额，直接跳过后续更大的硬币
            if coin > remaining:
                break
            path.append(coin)
            # 下一次递归从i开始，允许重复选同面值硬币；如果不允许重复选就传i+1
            backtrack(remaining - coin, path, i)
            # 回溯：只删除刚才追加的这一个硬币
            path.pop()
    backtrack(amount, [], 0)
    return result

# 测试
output = make_change(6, (1,3,4))
print(output)
# 输出：[[1, 1, 1, 1, 1, 1], [1, 1, 1, 3], [1, 1, 4], [3, 3]]

• 不要使用全局变量：全局变量在递归、多线程场景下非常容易出现不可预期的错误，优先用闭包或者参数传递存储中间结果。
• 递归函数如果不需要返回值就不要赋值接收，你原代码里print(output)会输出None，因为MakeTree没有return语句。
• 常量尽量提前计算：比如max(coins)可以在函数最开始算一次，不要每次循环都重复计算。
• 遵循Python命名规范：函数名用小写加下划线的蛇形命名，不要用大驼峰（大驼峰一般用来命名类）。
• 善用列表的pop()方法：删除末尾元素直接用lst.pop()即可，比del lst[-1]可读性更高。

内容的提问来源于stack exchange，提问作者Gurjot Singh Sidhu