program Partitions;
{ Print a partition stored in 'arr' in the form "a + b + c" }
procedure PrintArray(arr: array of Integer; size: Integer);
var
i: Integer;
begin
for i := 0 to size - 1 do
begin
if i > 0 then
Write(' + '); { add plus signs between numbers }
Write(arr[i]);
end;
WriteLn;
end;
{
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.
}
procedure Partitions(var arr: array of Integer; size, start, remaining: Integer);
var
j: Integer;
begin
{ Base case: exact sum reached }
if remaining = 0 then
begin
if size >= 2 then { enforce "two or more integers" }
PrintArray(arr, size);
Exit;
end;
{ Try all next values from 'start' up to 'remaining' }
for j := start to remaining do
begin
arr[size] := j; { choose j }
Partitions(arr, size + 1, j, remaining - j); { recurse with reduced remainder }
{ no need to "pop" in Pascal; we just overwrite next time }
end;
end;
var
n: Integer;
arr: array[0..128] of Integer; { holds current partition (large enough buffer) }
begin
n := 5; { number to partition }
Partitions(arr, 0, 1, n); { start with smallest allowed value = 1 }
end.
(*
run:
1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 3
1 + 2 + 2
1 + 4
2 + 3
*)
