Question

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

Answer 1

// Print a partition stored in 'arr' in the form "a + b + c"
function printArray(arr: number[], size: number): void {
    let line: string = "";

    for (let i: number = 0; i < size; i++) {
        if (i > 0) line += " + ";   // add plus signs between numbers
        line += arr[i].toString();
    }

    console.log(line);
}

/*
    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: number[], size: number, start: number, remaining: number): void {

    // 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: number = 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 TypeScript; we just overwrite next time
    }
}

function main(): void {
    const n: number = 5;                 // number to partition
    const arr: number[] = 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: partitions(4) returns:
 * [
 *   [4],
 *   [3,1],
 *   [2,2],
 *   [2,1,1],
 *   [1,1,1,1]
 * ]
 */

export function partitions(n: number): number[][] {
  const results: number[][] = [];

  /**
   * Backtracking helper
   * @param remaining - how much is left to sum to
   * @param max - largest allowed next number (to keep order non‑increasing)
   * @param current - current partial partition
   */
  function backtrack(remaining: number, max: number, current: number[]) {
    // If nothing remains, we found a valid partition
    if (remaining === 0) {
      results.push([...current]);
      return;
    }

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

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


console.log(partitions(5));



/*
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