递归实现硬币找零：如何将结果改为列表的列表形式？

我来帮你搞定这个问题！原代码的问题在于它把所有硬币都扁平地拼在一个列表里，还混入了无效的-1，完全没区分开不同的找零方案。咱们得调整递归的思路，改成收集每一条完整的有效路径，最终输出列表的列表格式。

修改后的实现思路 #

我们用回溯法来实现：通过递归尝试每一种硬币组合，当剩余金额刚好减到0时，就把当前的找零路径存入结果列表；如果剩余金额小于0，就直接回退，放弃这条无效路径。

完整代码 #

def coin_change(coins, target):
    # 用来存储所有有效找零方案的大列表
    result = []
    
    def backtrack(remaining, current_path):
        # 剩余金额为0，说明找到一个有效方案，存入结果
        if remaining == 0:
            # 必须复制当前路径，避免后续修改影响已存入的结果
            result.append(current_path.copy())
            return
        # 剩余金额小于0，这条路走不通，直接返回
        if remaining < 0:
            return
        # 遍历每个硬币，尝试加入当前路径
        for coin in coins:
            current_path.append(coin)
            # 递归处理减去当前硬币后的剩余金额
            backtrack(remaining - coin, current_path)
            # 回溯：移除刚加入的硬币，尝试下一个硬币
            current_path.pop()
    
    # 启动回溯，初始剩余金额是目标值，路径为空
    backtrack(target, [])
    return result

# 测试你的示例
coins = [3,10,7]
target = 5
print(coin_change(coins, target))  # 输出：[]（因为3、7、10都无法凑出5）

额外优化：避免重复方案 #

如果觉得[1,2,2]和[2,1,2]属于同一种找零方案（只是顺序不同），可以调整递归逻辑，让每个方案只按硬币的原有顺序组合，避免重复。修改后的回溯函数如下：

def backtrack(remaining, current_path, start_index):
    if remaining == 0:
        result.append(current_path.copy())
        return
    if remaining < 0:
        return
    # 从start_index开始遍历，只选当前及之后的硬币，避免顺序不同的重复方案
    for i in range(start_index, len(coins)):
        coin = coins[i]
        current_path.append(coin)
        backtrack(remaining - coin, current_path, i)
        current_path.pop()

# 启动时start_index设为0
backtrack(target, [], 0)

比如用coins=[1,2,5]、target=5测试，优化后的输出会是：

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

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