An efficient algorithm for generating integer partitions

A partition of an integer $n$ is a way of writing it as a sum of positive integers where order does not matter. For $n=5$ there are seven:

$5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1$

There are two different problems hiding here, and mixing them up is the usual source of confusion. Generating every partition and counting how many there are have very different costs.

Generating them

To enumerate partitions without producing the same one twice, fix an order: always emit parts in non-increasing size. Then each recursive call only needs to know how much is left and the largest part it is still allowed to use.

func partitions(n int) [][]int {
	var result [][]int
 
	var build func(remaining, maxPart int, current []int)
	build = func(remaining, maxPart int, current []int) {
		if remaining == 0 {
			result = append(result, slices.Clone(current))
			return
		}
		for part := min(remaining, maxPart); part >= 1; part-- {
			build(remaining-part, part, append(current, part))
		}
	}
 
	build(n, n, nil)
	return result
}

The two highlighted lines are the whole algorithm. Counting down from min(remaining, maxPart) picks each candidate largest part in turn, and passing part as the next call's maxPart is what enforces the non-increasing order — that single constraint is what stops 3+2 and 2+3 from both appearing.

Running it for $n=5$ gives exactly the seven partitions above, in that order.

Counting them

Counting is a different story, and here caching does pay. Ask a narrower question: how many partitions of $s$ use only parts of size at most $p$? Work through the allowed part sizes one at a time, and each new size just adds to what you already had.

func countPartitions(n int) int {
	counts := make([]int, n+1)
	counts[0] = 1
	for part := 1; part <= n; part++ {
		for sum := part; sum <= n; sum++ {
			counts[sum] += counts[sum-part]
		}
	}
	return counts[n]
}

counts[0] = 1 seeds the recurrence: there is exactly one way to make zero, namely the empty partition. After the outer loop finishes with part, counts[s] holds the number of partitions of s using parts no larger than part. Sweeping sum upward rather than downward is what allows a part to be used more than once.

Two nested loops over $n$ gives $O(n^2)$ time and $O(n)$ space:

The gap is dramatic. $p(100)=190{,}569{,}292$, so generating all of them is hopeless — but counting them finishes in about ten thousand operations.

Constraining the number of parts

If you also need to bound how many parts a partition may have, add that dimension to the state. Let $f[s][m][k]$ be the number of partitions of $s$ into exactly $m$ non-decreasing parts whose largest part is $k$. The transition extends a partition by a new part $l$ that is at least as large as the current one:

$f[s][m][k]\to f[s+l][m+1][l] \quad \text{for every } l\geq k$

Summing over $k$ at the end gives the count for a given $s$ and $m$. There are $n\times m$ states and each tries every valid last value, so this costs $O(n^2\times m)$.

That extra factor buys you a question the one-dimensional version cannot answer — which is the usual trade in dynamic programming. You pay for state only when you need to distinguish something.