要素の合計であるすべてのサブセットを見つける方法は定数に等しいか？

Question

数字を取得するには、すべての数字のサブセットを見つける必要があります。Nの要素を合計します。私はどのようにこの種の組み合わせ問題を解決するのか分かりません。この組み合わせでは、異なる番号の注文が重要です。

1 + 1 + 1 + 1 
2 + 1 + 1 
1 + 2 + 1 
1 + 1 + 2 
2 + 2 
3 + 1 
1 + 3 

ゼロ数N = 4のための

の例では、私のために重要ではありません。だから、どのように正確な数の配列としてそのような数値セットを得ることができますか？

Answer 1

あなたが探しているものは、整数compositions、またはpartitionsと呼ばれています。テストされていない

public static IEnumerable<List<int>> Compositions(int n) 
{ 
    if (n < 0) 
     throw new ArgumentOutOfRangeException(nameof(n)); 

    return GenerateCompositions(n, new List<int>()); 
} 

private static IEnumerable<List<int>> GenerateCompositions(int n, List<int> comp) 
{ 
    if (n == 0) 
    { 
     yield return new List<int>(comp); // important: must make a copy here 
    } 
    else 
    { 
     for (int k = 1; k <= n; k++) 
     { 
      comp.Add(k); 

      foreach (var c in GenerateCompositions(n - k, comp)) 
       yield return c; 

      comp.RemoveAt(comp.Count - 1); 
     } 
    } 
} 

：

組成物は、以下のように（私は間違っていない場合は、辞書式順序で）再帰的に生成することができます！これはPythonの実装から転写されました。誰でも慣れ親しんだC＃でコードを修正したり、コードを更新したい場合は、自由に感じてください。また

、as @aah noted、nの組成物の数は2^(n-1)ので、これも適度nために扱いにくくなります。

Answer 2

順序が重要でない場合、単純に2 ^（N-1）個の可能性があります。 （あなたの例に2 + 2または4がありません）

これで、任意のシーケンスを2進表現で表すことができます。生成するには、N 1を連続して想像してください。その間にN-1個の「スペース」があります。スペースのサブセットを選択すると、選択したスペースを介して隣接する1つをマージします。このようなシーケンスを展開し、これらのスペースを挿入することによって、これがすべての可能なセットに対して1-1であることを確認できます。