硬币找零问题python递归

硬币找零问题是经典的计算机科学问题，通常涉及给定一组面额，计算如何组合这些面额以获得给定的目标金额。使用Python递归解决这个问题，我们可以创建一个函数，该函数会尝试用当前可用的最大面额去覆盖剩余的金额，并返回所有可能的解决方案。

以下是一个简单的Python递归示例：

def coin_change(coins, amount):
    # 基本情况：如果目标金额是0，直接返回空列表表示找到了零钱组合
    if amount == 0:
        return [[]]
    
    # 如果当前最大面额大于目标金额，说明无法找到组合
    if coins[0] > amount:
        return []
    
    # 递归情况：尝试将最大面额加入到可能的组合中，然后递归处理剩余金额
    result = []  # 存储所有可能的组合
    for i in range(len(coins)):
        # 考虑当前面额是否能用，如果可以，则添加它到结果中，并从剩余金额中减去这个面额
        sub_result = coin_change(coins[i+1:], amount - coins[i])
        
        # 如果sub_result中有解，将其与当前面额组合并加入result
        if sub_result:
            for r in sub_result:
                result.append([coins[i]] + r)
    
    return result

# 示例
coins = [1, 2, 5]
amount = 11
print(coin_change(coins, amount))  # 输出所有可能的找零方案