x個の数字のすべての組み合わせを見つけてください。Yの値は

Question

です。

私はPHPでこの解決策を書こうとしています。

入力：私は非常に大きな数を扱っていないよ

number of numbers = x 
smallest number = 1 
sum of numbers = y 

は、最大xはapproximatly 50であり、最大yはapproximatly 80

ルールである：数字の各セット内、数手続前の値はそれ以上でなければなりません。

例えば

x = 3 
min = 1 
y = 6 

溶液：（3,2,1）のような解決策ではないこと （1,1,4）、（1,2,3）

メモ彼らは降順になっています。

Answer 1

これは再帰によって簡単に解決されます。しかし時間の複雑さは高くなるでしょう。より良い（ただし少し複雑なソリューション）には、動的プログラミングを使用してください。セットのサイズは1はその後、唯一の可能な解決策が必要な和である場合

：

は、ここで考えです。

セットは、あなたが最小と希望和マイナスX.まで追加番号のセットを用いて所望の和の間の数Xをマージすることができます1よりも大きい場合

function tuplesThatSumUpTo($desiredSum, $minimumNumber, $setSize) { 
     $tuples = []; 
     if ($setSize <= 1) { 
      return [ [ $desiredSum ] ]; //A set of sets of size 1 e.g. a set of the desired sum 
     } 
     for ($i = $minimumNumber;$i < $desiredSum;$i++) { 
      $partial = tuplesThatSumUpTo($desiredSum-$i, $minimumNumber,$setSize-1); 
      $tuples = array_merge($tuples, array_map(function ($tuple) use ($i) { 
       $res = array_merge([$i], $tuple);   
       sort($res); 
       return $res; 
      },$partial)); 
     } 
     return array_unique($tuples,SORT_REGULAR); 
} 

は、それが実行を参照してください。 ：

http://sandbox.onlinephpfunctions.com/code/1b0e507f8c2fcf06f4598005bf87ee98ad2505b3

動的プログラミングアプローチは、あなたの代わりに部分和とのセットの配列を保持し、あなたが後で必要なものを埋めるためにそれに戻って参照する必要があります。