Integer partitioning in 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 :).

Feels like some programming challenge.. i am afraid any one will write a code for you . — M A SIDDIQUI
– M A SIDDIQUI, Commented Feb 17, 2017 at 6:30
Typing "integer partitioning" in the search box returns 1,324 results. Are you sure none of those questions and answers helped you? — m69 ''snarky and unwelcoming''
– m69 ''snarky and unwelcoming'', Commented Feb 17, 2017 at 22:52

Fallen · Accepted Answer · 2017-02-17 06:42:38Z

4

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:

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.

answered Feb 17, 2017 at 6:42

Fallen

4,5833 gold badges30 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Integer partitioning in PHP

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related