Question

How to find all possible ways to write a positive integer as a sum of positive integers in PHP

Answer 1

// Print a partition stored in 'arr' in the form "a + b + c"
function print_array_partition($arr, $size) {
    for ($i = 0; $i < $size; $i++) {
        if ($i > 0) echo " + ";   // add plus signs between numbers
        echo $arr[$i];
    }
    echo "\n";
}

/*
    Generate all partitions of a number using non-decreasing sequences.

    arr       – current partial partition being built
    size      – how many elements are currently in arr
    start     – the smallest number allowed next (prevents duplicates like 2+1 vs 1+2)
    remaining – how much is left to reach the target sum

    When remaining == 0, arr contains a complete valid partition.
*/
function partitions(&$arr, $size, $start, $remaining) {

    // Base case: exact sum reached
    if ($remaining == 0) {
        if ($size >= 2)      // enforce "two or more integers"
            print_array_partition($arr, $size);
        return;
    }

    // Try all next values from 'start' up to 'remaining'
    for ($j = $start; $j <= $remaining; $j++) {
        $arr[$size] = $j;                          // choose j
        partitions($arr, $size + 1, $j, $remaining - $j);  // recurse with reduced remainder
        // no need to "pop" in PHP; we just overwrite next time
    }
}

$n = 5;                 // number to partition
$arr = array_fill(0, 128, 0);   // holds current partition (large enough buffer)

partitions($arr, 0, 1, $n);     // start with smallest allowed value = 1



/*
run:

1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 3
1 + 2 + 2
1 + 4
2 + 3

*/

 

70+ SQL courses for beginners and professionals

Answer 2

/**
 * Generate all ways to write a positive integer n
 * as a sum of positive integers (integer partitions).
 *
 * Example for n = 5:
 * [
 *   [5],
 *   [4, 1],
 *   [3, 2],
 *   [3, 1, 1],
 *   [2, 2, 1],
 *   [2, 1, 1, 1],
 *   [1, 1, 1, 1, 1]
 * ]
 */

/**
 * Returns all partitions of a positive integer.
 *
 * @param int $n  The number to partition.
 * @return array  Array of partitions.
 */
function partitions(int $n): array {
    $results = [];

    /**
     * Backtracking helper.
     *
     * @param int   $remaining  How much is left to reach n.
     * @param int   $max        Maximum allowed next number.
     * @param array $current    Current partial partition.
     */
    $backtrack = function($remaining, $max, $current) use (&$results, &$backtrack) {
        // If nothing remains, we found a valid partition
        if ($remaining === 0) {
            $results[] = $current;
            return;
        }

        // Try next numbers from max down to 1
        for ($next = min($remaining, $max); $next >= 1; $next--) {
            $newCurrent = $current;
            $newCurrent[] = $next; // choose
            $backtrack($remaining - $next, $next, $newCurrent); // explore
        }
    };

    $backtrack($n, $n, []);

    return $results;
}

// Run the program:
$result = partitions(5);
print_r($result);



/*
run:

Array
(
    [0] => Array
        (
            [0] => 5
        )

    [1] => Array
        (
            [0] => 4
            [1] => 1
        )

    [2] => Array
        (
            [0] => 3
            [1] => 2
        )

    [3] => Array
        (
            [0] => 3
            [1] => 1
            [2] => 1
        )

    [4] => Array
        (
            [0] => 2
            [1] => 2
            [2] => 1
        )

    [5] => Array
        (
            [0] => 2
            [1] => 1
            [2] => 1
            [3] => 1
        )

    [6] => Array
        (
            [0] => 1
            [1] => 1
            [2] => 1
            [3] => 1
            [4] => 1
        )

)

*/

 

70+ SQL courses for beginners and professionals