php - 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。存在一些动态规划解决方案可以解决更大范围内数字的问题。