再帰バックトラッキングmakeChange

Question

再帰的バックトラッキングを使用して、ペニー（1セント）、ニッケル（5セント）、ダイム（10セント）、および四半期（25セント）を使用して、セント）。 37セントで変更を行う際

たとえば、あなたが使用することができます：

1ダイム

• 1四半期と2ペニー
• 3ダイムと7ペニー
• またはその他の組み合わせ。

あなたのメソッドは、1つのパラメータを受け入れる必要があります。変更するセントの量。

あなたのメソッドの出力は、1行に1つずつ、その金額に加算される各タイプのコインのすべての組み合わせのシーケンスでなければなりません。

たとえば、クライアントコードは、次の呼び出しが含まれる場合：

System.out.println(" P N D Q"); 
System.out.println("------------"); 
makeChange(28); 

を生成し、全体的な出力は次のようする必要があります。

P N D Q 
------------ [3, 0, 0, 1] [3, 1, 2, 0] [3, 3, 1, 0] [3, 5, 0, 0] [8, 0, 2, 0] [8, 2, 1, 0] [8, 4, 0, 0] [13, 1, 1, 0] [13, 3, 0, 0] [18, 0, 1, 0] [18, 2, 0, 0] [23, 1, 0, 0] [28, 0, 0, 0] 

この問題を解決に向けた重要な洞察がの概念でありますコイン（ペニー、ニッケルなど）の各貨幣を見て、そのコインの可能なすべての数（1ペニー、2ペニー、...、28ペニー）を試して、その選択からどのような組み合わせを作ることができるかを見てください。たとえば、上記の出力では、まず3ペニーで始まるすべての組み合わせが表示され、次に8ペニーで始まるすべての組み合わせなどが表示されます。

バックトラックには一連の選択肢が含まれているため、コード内に何らかの形でコインの金種を表す必要があります。処理のためにすべてのコイン金種の値のリストを保持することをお勧めします。さまざまなコインの価値を処理するときに、このリストの内容を変更することができます。以下のテンプレートは、（あなたが/コピーあなたのコードのテキストボックスに貼り付けることができます始めるために）出発点である：

public static void makeChange(int amount) { 
    List coinValues = new LinkedList(); 
    coinValues.add(1); // penny 
    coinValues.add(5); // nickel 
    coinValues.add(10); // dime 
    coinValues.add(25); // quarter 

// ... your code goes here ... 

はあなたのメソッドに渡された変化量が非負であることを前提としていますが、それもそこでここでは100

を超える可能性が私のコードです：

public static void makeChange(int amount){ 
    int[] acc = new int[4]; 
    makeChange(amount, acc); 
} 

private static void makeChange(int amount, int[] acc){ 
    if(amount == 0){ 
     System.out.print("[" + acc[0]); 
     for(int i = 1; i < 4; i++){ 
      System.out.print(", " + acc[i]); 
     } 
     System.out.print("]"); 
     System.out.println(); 
    } 
    if(amount > 0){ 
     acc[0]++; 
     makeChange(amount - 1, acc); 
     acc[0]--; 
     acc[1]++; 
     makeChange(amount - 5, acc); 
     acc[1]--; 
     acc[2]++; 
     makeChange(amount - 10, acc); 
     acc[2]--; 
     acc[3]++; 
     makeChange(amount - 25, acc); 
     acc[3]--; 
    } 
} 

とmakeChange（28）の呼び出しのために、その出力：

[28, 0, 0, 0] 
[23, 1, 0, 0] 
[23, 1, 0, 0] 
[23, 1, 0, 0] 
[23, 1, 0, 0] 
[23, 1, 0, 0] 
[23, 1, 0, 0] 
[18, 2, 0, 0] 
[18, 0, 1, 0] 
[23, 1, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 0, 1, 0] 
[23, 1, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 0, 1, 0] 
[23, 1, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 0, 1, 0] 
[23, 1, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 0, 1, 0] 
[23, 1, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[18, 0, 1, 0] 
[13, 1, 1, 0] 
[23, 1, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[18, 0, 1, 0] 
[13, 1, 1, 0] 
[13, 1, 1, 0] 
[23, 1, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[18, 0, 1, 0] 
[13, 1, 1, 0] 
[13, 1, 1, 0] 
[13, 1, 1, 0] 
[23, 1, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[18, 0, 1, 0] 
[13, 1, 1, 0] 
[13, 1, 1, 0] 
[13, 1, 1, 0] 
[13, 1, 1, 0] 
[23, 1, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[18, 2, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 

...（何百行もの出力があります）

なぜ出力が重複するのか教えていただけますか？ ありがとうございます！

Answer 1

簡単な言い方をすると、同じソリューションでさまざまなルートで到着しました。さて、コードは注文事項に書かれています。理解する

シンプルなケース：

は、私たちが今、6 の変更をしたいとします。

したがって[1,1,0,0]は2回解決されます。

ウェイ1：あなたは5、その後、最初の1を減算し、0

ウェイ2に達した：あなたは1、その後、最初の5を減算し、唯一のユニークなソリューションは、にHashSetまたはTreeSetを使用取得するには0

に達したがストアの解決策は基本条件で印刷する代わりにArrayList（配列ではない）とすることができます。すべてのソリューションを最後に一緒に印刷します。

もう1つの方法は、最後に使用したコインを示す3番目のパラメータを追加することです。最後に使用した硬貨に金額>=のコインを使用します。これにより、ソリューションが一意になることが保証されます。