algorithm - 印刷硬币图案

Question

可能重复：
递归进行更改：如何修改我的算法以打印所有组合？

在硬币图案计数问题中（给定一个值 N 和一组固定的硬币，我们必须计算加起来为 N 的硬币组合的数量。），如果我们想打印组合而不是计算组合，什么是该方法 ？我必须为此使用动态编程吗？

Answer 1

是的，你需要它。假设dp[i]等于加起来的组合数，i则以下伪代码打印所有组合：

print_combinations(amount_left, current_coin):
    if amount_left == 0:
        print "\n"
        return
    if current_coin == num_coins:
        return
    if dp[amount_left - coins[current_coin]] > 0:
        print coins[current_coin], " "
        print_combinations(amount_left - coins[current_coin], current_coin)
    print_combinations(amount_left, current_coin + 1)

此函数打印coins [current_coin .. last_coin]加起来为 amount_left 的所有组合。所以最初的调用是print_combinations(N, 0)，正如你所看到的，动态规划表dp[]帮助我们决定是否使用当前硬币进行递归（我们只有在至少有一个组合加起来等于剩余的新数量时才会递归amount_left - coins[current_coin]）。