PHP中的整数分区

Question

This feels like a very simple problem, but I can't manage to make it elegant and 'feels right'. Here's the problem:

Giving a number T, print out all possible ways to get to T. For example :

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

Note that, 3 + 2 is equal than 2 + 3, so you don´t have to print both cases.

I have to do it in PHP, hope anyone can help :).

Answer 1

One easy way to solve this problem is to solve it recursively. Following is a sample code,

<?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, []);

Output:

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

Note that, this bruteforce recursive solution won't work for bigger T. There exist some dynamic programming solutions which can solve this problm for numbers in a larger range.