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[]は、現在のコインを使用して再帰するかどうかを決定するのに役立ちます（少なくとも1つの組み合わせが残っている場合にのみ再帰しamount_left - coins[current_coin]ます）。