与えられた集合から与えられた数（繰り返しが許される）を合計するすべての方法を見つける

Question

n個の要素の配列（例えば[1,2]）と数 'k'（例えば6）を与えた場合、合計= K

私は考えることができアルゴリズムは力ずくである

1 1 1 1 1 1 
1 1 1 1 2 
1 1 2 2 
2 2 2 

ので、与えられた例の答えは4になりますため、我々はすべての可能なシナリオをシミュレートし、与えられた状態から、我々は結果に到達できないときに停止。

arr[] = [1,2] 
    k = 6 
    globalCount =0; 
    function findSum(arr,k) 
    { 
     if(k ==0) 
     globalCount++ 
     return 
     else if(k<0) 
     return 

     for each i in arr{ 
     arr.erase(i) 
     tmp = k 
     findSum(arr,tmp) 
     while(k>=0){ 
      findSum(arr,tmp -= i) 
     } 
    } 

私は私の解決策は、そこに最も効率的なものであればわかりません。コメントしてください/正しいか、より良い解決策への指針を示してください。

EDIT：誰かが私のコードとsolnコードの実行時の複雑さを私に与えることができたら本当に感謝します。 ） 地雷コードの複雑さ私が思うに、Big-O（n^w）w = k/avg（arr [0] .. arr [n-1]）

Answer 1

あなたは素晴らしいlinqのトリックを口実にして喜んでいるなら、このC＃ソリューションが役立つかもしれません。幸いにもlinqは英語のようなものを読みます。考え方は、kが0から始まり、正しい値に達するまで増分するようにソリューションを構築することです。 kの各値は、以前のソリューションに基づいています。あなたが見なければならないことの1つは、あなたが探している新しい「方法」が他人の並べ替えではないことを確実にすることです。私はそれがソートされていれば有効とカウントするだけで解決しました。 （これは、単一の比較であった）

void Main() { 
    foreach (int[] way in GetSumWays(new[] {1, 2}, 6)) { 
     Console.WriteLine (string.Join(" ", way)); 
    } 
} 

int[][] GetSumWays(int[] array, int k) { 
    int[][][] ways = new int[k + 1][][]; 
    ways[0] = new[] { new int[0] }; 

    for (int i = 1; i <= k; i++) { 
     ways[i] = (
      from val in array 
      where i - val >= 0 
      from subway in ways[i - val] 
      where subway.Length == 0 || subway[0] >= val 
      select Enumerable.Repeat(val, 1) 
       .Concat(subway) 
       .ToArray() 
     ).ToArray(); 
    } 

    return ways[k]; 
} 

出力：これは、動的プログラミングアプローチを使用して、ナイーブな再帰的なアプローチよりも速くなければならない

1 1 1 1 1 1 
1 1 1 1 2 
1 1 2 2 
2 2 2 

。おもう。私はそれが数ミリ秒でドルを壊す方法の数を数えるのに十分に速いことを知っています。 （242）

Answer 2

これは興味深い部分的な問題のサブセットです。すべての整数を許可する場合は、実際には閉鎖型のソリューション（hereおよびhereを参照）があります。

「制限されたパーティション機能」でグーグルをやっていると、私にいくつかのリードが与えられました。 This paperは、this oneのように、この問題に対するいくつかの解決法を数学的に厳密に議論しています。

残念ながら、私はこれらをコード化するのが面倒です。彼らはかなり強いソリューションです。