在PHP中的整数分区

Question

这感觉就像一个非常简单的问题，但我无法设法让它变得优雅和“感觉很好”。这里的问题：

给予了一些T，打印出所有可能的方式去T. 例如：

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

需要注意的是，3 + 2比2 + 3等于，所以你不要不必打印这两种情况。

我必须在PHP中做到这一点，希望任何人都可以帮助:)。

Answer 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 

需要注意的是，这种暴力破解递归解决方案不会为较大的T.存在一些动态规划的解决方案，可以解决这个problm换号工作在一个更大的范围内。