为什么我写的凑硬币组合的Python代码会重复输出大量相同结果？

• 递归分支结构错误：你将「选取当前面值硬币」和「跳过当前面值硬币」两个独立的递归分支写成了嵌套关系，每触发一次选当前硬币的逻辑，都会额外执行一遍跳过当前硬币的全量递归，导致同一组合被重复生成成千上万次，递归调用量指数级上涨，运行极慢。
• 冗余计算开销：每次调用sum(coins_so_far)计算当前已选金额，属于无意义的重复计算，进一步拖慢运行速度。

def change(remaining, coins_available, coins_so_far):
    if remaining == 0:
        yield coins_so_far.copy()
    elif remaining < 0 or not coins_available:
        return
    else:
        # 分支1：选当前第一个面值的硬币，保留该面值在可选列表中（允许重复选同面值）
        coins_so_far.append(coins_available[0])
        yield from change(remaining - coins_available[0], coins_available, coins_so_far)
        coins_so_far.pop()
        # 分支2：不选当前第一个面值的硬币，从可选列表中移除，后续不会再选该面值
        yield from change(remaining, coins_available[1:], coins_so_far)

n = 30
coins = [1, 5, 10, 25, 100]
solutions = list(change(n, coins, []))
print(f"总组合数：{len(solutions)}")
for s in solutions:
    print(s)

• 两个递归分支调整为平行结构，严格按给定硬币顺序选择，不会回头选已经跳过的面值，从根源上避免了同组合的不同排列重复出现，也不会重复触发递归。
• 用剩余待凑金额代替已选金额求和计算，省去重复求和开销，运行效率大幅提升。
• 用yield from简化递归生成器的写法，逻辑更清晰。

测试验证：n=30时运行仅返回18种不重复的合法组合，无冗余输出，运行耗时可以忽略。

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