Question

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

Answer 1

// Print a partition stored in 'arr' in the form "a + b + c"
function printArray(arr, size) {
    for (let i = 0; i < size; i++) {
        if (i > 0) process.stdout.write(" + ");   // add plus signs between numbers
        process.stdout.write(String(arr[i]));
    }
    process.stdout.write("\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"
            printArray(arr, size);
        return;
    }

    // Try all next values from 'start' up to 'remaining'
    for (let 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 JavaScript; we just overwrite next time
    }
}

function main() {
    let n = 5;                 // number to partition
    let arr = new Array(128).fill(0);  // holds current partition (large enough buffer)

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

main();


/*
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 {number} n - The number to partition.
 * @returns {number[][]} - Array of partitions.
 */
function partitions(n) {
  const results = [];

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

    // Try all next numbers from max down to 1
    for (let next = Math.min(remaining, max); next >= 1; next--) {
      current.push(next);                 // choose
      backtrack(remaining - next, next, current); // explore
      current.pop();                      // un-choose (backtrack)
    }
  }

  backtrack(n, n, []);
  return results;
}

// Run the program:
const result = partitions(5);
console.log(result);



/*
run:

[
  [ 5 ],
  [ 4, 1 ],
  [ 3, 2 ],
  [ 3, 1, 1 ],
  [ 2, 2, 1 ],
  [ 2, 1, 1, 1 ],
  [ 1, 1, 1, 1, 1 ]
]

*/

 

70+ SQL courses for beginners and professionals