印刷硬幣圖案

Question

可能重複：
Making change recursively: How do I modify my algorithm to print all combinations?

在硬幣圖案計數問題（給定一個值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]）。