PHPでの整数パーティション

Question

これは非常に単純な問題のように感じますが、私はそれをエレガントにすることはできません。ドンあなたはので、3 + 2 2 + 3と同等である、ということ

T = 5 
1 + 1 + 1 +1 + 1 
2 + 1 + 1 + 1 
3 + 1 + 1 
2 + 2 + 1 
4 + 1 
3 + 2 

注：たとえばT. に取得するすべての可能な方法をプリントアウトし、

数Tを与える：ここで問題ですどちらの場合も印刷する必要があります。

私はPHPでそれをやる必要があります、誰も助けることができる願って:)。

Answer 1

この問題を解決する簡単な方法の1つは、再帰的に解決することです。サンプルコードを以下に示し、

<?php 
function recursion($left, $last, $ar) { 
    if($left == 0) { 
     foreach ($ar as $n) { 
      printf("%d ", $n); 
     } 
     print "<br>"; 
     return; 
    } 
    for($n = $last; $n <= $left; $n++) { 
     $b = $ar; 
     array_push($b, $n); 
     recursion($left - $n, $n, $b); 
    } 
} 

recursion(5, 1, []); 

出力：

1 1 1 1 1 
1 1 1 2 
1 1 3 
1 2 2 
1 4 
2 3 
5 

（注）このブルートフォース再帰的な解決策は、数字のために、このproblmを解決することができ、いくつかの動的なプログラミングソリューションを存在はあり大きなT.のために動作しません、より広い範囲で。