intとnの配列が与えられた場合、intsを使用してnと合計するウェイの数を計算します

Question

インタビューの準備でこの問題を見ました。

はintの配列及び数nが与えられると、

次のコードは、私の解決策であるint型を使用してnに 和する方法の数を計算します。私は再帰によってこれを解決しようとしました。サブ問題は配列内の各intに対してです。それを選択することもできません。

public static int count(List<Integer> list, int n) { 
    System.out.print(list.size() + ", " + n); 
    System.out.println(); 
    if (n < 0 || list.size() == 0) 
     return 0; 
    if (list.get(0) == n) 
     return 1; 
    int e = list.remove(0); 
    return count(list, n) + count(list, n - e); 
    } 

私は[10、1、2、7、6、1、5] int型に使用する試み、および8 nに結果セットが4.ただし、Iは0を得なければならない私はしようとしましたコードで示されているように、スタックの各レイヤーでデバッグするものを印刷します。以下は私が持っているものです：

7, 8 
6, 8 
5, 8 
4, 8 
3, 8 
2, 8 
1, 8 
0, 8 
0, 3 
0, 7 
0, 2 
0, 1 
0, 6 
0, 7 
0, -2 

この結果は私を混乱させます。私はそれが最初から（0,3）に見えると思う。 （0、7）から始まって、それは私に間違って見えます。私はそこに（1,7）を期待する。なぜなら、私が正しく理解すれば、これはcount（list、n - e）コールがスタックの最下位レイヤーに2番目にあるからです。下位層のリスト操作は、現在の層のリストに影響を与えるべきではありません。 私の質問は次のとおりです：

1. なぜ私の現在のコードに基づいて（1,7）の代わりに（0、7）ですか？
2. 正しい結果を得るために現在のコードに対してどのような調整を行う必要がありますか？

ありがとう！

Answer 1

アルゴリズムが機能しない理由は、再帰呼び出しの前に変更されているリストを1つ使用しているためです。

リストを参照で渡さあるので、何が起こって終わると、リストでは何がこれ以上存在しなくなるまで、あなたが再帰的にremoveを呼び出した後、あなたの再帰呼び出しのすべてが0

何を返すしようとしているということですすべての再帰的ステップでリストの2つのコピーを作成することができます。しかし、これはあまりにも非効率的です。あなたは、初期関数呼び出しにiためyourList.size() - 1を通過する

public static int count(List<Integer> list, int n, int i) { 
    //System.out.print(list.size() + ", " + n); 
    //System.out.println(); 
    if (n < 0 || i <= 0) 
     return 0; 

    int e = list.get(i); // e is the i-th element in the list 
    if (e == n) 
     return 1 + count(list, n, i-1); // Return 1 + check for more possibilities without picking e 

    return count(list, n, i-1) + count(list, n - e, i-1); // Result if e is not picked + result if e is picked 
} 

：

より良い方法は、通話中に見られているリスト内の要素をマークインデックスiを使用することです。

もう一つのポイントは、あなたの要素eがないときにreturn 1、あなたはまだのために多くの可能性を追加しなければならないときは、和の一部であることをを選んだということです。そうでない場合、たとえばリストの最後の要素がnだった場合、再帰は最初の手順では1を返すだけで終了し、より多くの可能な数値の組み合わせはチェックされません。

最後に、動的アプローチを使用してアルゴリズムを書き直したい場合は、の方が実行時間がより良いとなるでしょう。