= Solution
Write parts in nonincreasing order. The <array> `part` stores the current prefix, and `Emit(i,r,len)` completes it using parts at most $i$ with remaining sum $r$. With `Out` as the <Oberon> output module:
``
VAR part: ARRAY MaxParts OF INTEGER;
PROCEDURE Emit(i, r, len: INTEGER);
VAR j: INTEGER;
BEGIN
IF r = 0 THEN
j := 0;
WHILE j < len DO
IF j > 0 THEN Out.Char("+") END;
Out.Int(part[j], 0); j := j+1
END;
Out.Ln
ELSIF i > 0 THEN
IF i <= r THEN
part[len] := i;
Emit(i, r-i, len+1)
END;
Emit(i-1, r, len)
END
END Emit;
PROCEDURE PrintPartitions(n: INTEGER);
BEGIN
Emit(n, n, 0)
END PrintPartitions;
``
The <recursion invariant> is that `part[0..len)` is nonincreasing, has sum $n-r$, and every further part must be at most $i$ and at most the last existing part. The first branch includes the next part $i$; the second excludes it. These alternatives partition all completions, so each <integer partition> is printed exactly once. A <recursive call> reduces $i+r$; the printing loop's <loop invariant> is that the first $j$ entries have been printed with exactly the necessary separators.
For $n>0$, no partition has more than $n$ parts, and the all-ones partition has exactly $n$. Thus \b[the fixed <array> requires $0\leq n\leq\texttt{MaxParts}$] to handle every partition. When a write occurs, $r>0$ and therefore `len < n`, so this bound prevents an out-of-range write. Zero prints one empty line, representing the empty <integer partition>. Available <call stack> space imposes a further practical limit.
Back to article page
