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