For a positive integer n, the partitions of n are all the possible different ways of writing n as the sum of positive integers.

For example, these are the possible partitions (7) for $n = 5$:

partitions(5):
5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 1 + 2
5 = 1 + 1 + 3
5 = 1 + 2 + 2
5 = 1 + 4
5 = 2 + 3
5 = 5


We don’t consider the particular order of the addends. That means that for us $5 = 2 + 3$ is the same partition of $5 = 3 + 2$.

## The problem

Given a positive integer $n$, compute all the partitions of $n$.

## The solution

This is a scala code snippet that solves the problem:

def partitions(n: Int): List[List[Int]] = partitions(n, 1)

def partitions(n: Int, m: Int): List[List[Int]] =
n match {
case _ if m > n => List()
case _ if m == n => List(List(n))
case _ if m < n =>
val ns1 = partitions(n - m, m).map { m :: _ }
val ns2 = partitions(n, m + 1)
ns1 ::: ns2
}


## Discussion

The solution is using a recursive description of what a partition is.

Looking back at our initial example for partitions of 5, we can easily guess the recursive structure of the list.

Take for example the partitions starting with 1. If we remove the leading 1, we have all the partitions for 4. For those starting with 2 , the remaining part is a partition of 3, and so on.

In general, if a partition of $n$ is starting with $k$, then the remaining addends form a partition of $n-k$.

In pseudo-code we can express this relation in the following way:

partitions(5) =
1 + partitions(4)
2 + partitions(3)
3 + partitions(2)
4 + partitions(1)
5 + partitions(0)


where with k + partitions(m) we mean the set of all the partitions of $k + m$ whose first addend is $k$ and the remaining addends form a partition of $m$.

There is one problem in this approach though, and it is that the same partition can occur multiple times. For example

5 = 1 + 2 + 2 // This belongs to 1 + partitions(4)
5 = 2 + 1 + 2 // This belongs to 2 + partitions(3)


This is a common problem in defining recursive algorithms that enumerate all the elements of a set: often the first recursive algorithm that comes to our mind does not guarantee unicity, and an extra step (or a different data structure, like a Set in our case) is necessary.

Let's now look how to achieve unicity without the need of an extra step.

1 + partitions(4) contains all the partitions with at least one 1. We can even say more: it is exactly that set, because obviously each partition in 1 + partitions(4) contains at least one 1.

To avoid repetitions, it is enough to consider, at the second step, the partitions of $3$ that do not contain any $1$.

partitions(5) =
1 + partitions(4, 1)
2 + partitions(4, 2)
...


where partitions(n, k) denotes the set of partitions of the number $n$ whose addends are greater or equal than $k$.

For example, partitions(4, 2) is formed only by the partitions $4 = 2 + 2$ and $4 = 4$, since any other partition of $4$ contains at least one $1$.

At that point, for the same argument, we will already have all the partitions that contain either a $1$ or a $2$, and we can complete our example:

partitions(5) =
1 + partitions(4, 1)
2 + partitions(3, 2)
3 + partitions(2, 3)
4 + partitions(1, 4)
5 + partitions(0, 5)


It's then enough to solve the following

### Problem 2

Given non-negative integers $n$ and $k$, compute all the partitions of $n$ composed by numbers greater or equal than $k$.

#### Base case

If $k > n$, clearly there are no such partitions. Therefore

partitions(n, k) = 0 if k > n


If $k = n$ there is only one.

partitions(n, k) = 1 if k = n


#### Inductive case

If $k < n$, we have two ways of building partitions of $n$ with elements greater or equal than $k$:
1. Partitions that contain $k$
2. Partitions that do not contain $k$

For case 1) we can take $k$ followed by all partitions of $n - k$ with numbers greater or equal than $k$. For the second case we take instead all the partitions of $n$ with numbers greater or equal than $k + 1$.

partitions(n, k) = partitions(n - k, k) + partitions(n, k + 1) if k > n


The algorithm always terminates because at each step the difference $n - k$ strictly decreases, so at some point we will reach the base case $n - k <= 0$.

We can put everything together and get our original scala snippet:

def partitions(n: Int): List[List[Int]] = partitions(n, 1)

def partitions(n: Int, m: Int): List[List[Int]] =
n match {
case _ if m > n => List()
case _ if m == n => List(List(n))
case _ if m < n =>
val ns1 = partitions(n - m, m).map { m :: _ }
val ns2 = partitions(n, m + 1)
ns1 ::: ns2
}


#### Compute only the number of partitions

If we just need to know the number of partitions of $n$, and not the full list of partitions, we can slightly modify the code to achieve that:

def numberOfPartitions(n: Int): Int = numberOfPartitions(n, 1)

def numberOfPartitions(n: Int, m: Int): Int =
n match {
case _ if m > n => 0
case _ if m == n => 1
case _ if m < n =>
numberOfPartitions(n - m, m) + numberOfPartitions(n, m + 1)
}


As we can see from the asymptotic formula for numberOfPartitions(n) below, the function grows pretty quickly. These are the values for $n <= 49$ (the values are taken from the wonderful encyclopedia of integer sequences):

partitions(0)  = 1
partitions(1)  = 1
partitions(2)  = 2
partitions(3)  = 3
partitions(4)  = 5
partitions(5)  = 7
partitions(6)  = 11
partitions(7)  = 15
partitions(8)  = 22
partitions(9)  = 30
partitions(10) = 42
partitions(11) = 56
partitions(12) = 77
partitions(13) = 101
partitions(14) = 135
partitions(15) = 176
partitions(16) = 231
partitions(17) = 297
partitions(18) = 385
partitions(19) = 490
partitions(20) = 627
partitions(21) = 792
partitions(22) = 1002
partitions(23) = 1255
partitions(24) = 1575
partitions(25) = 1958
partitions(26) = 2436
partitions(27) = 3010
partitions(28) = 3718
partitions(29) = 4565
partitions(30) = 5604
partitions(31) = 6842
partitions(32) = 8349
partitions(33) = 10143
partitions(34) = 12310
partitions(35) = 14883
partitions(36) = 17977
partitions(37) = 21637
partitions(38) = 26015
partitions(39) = 31185
partitions(40) = 37338
partitions(41) = 44583
partitions(42) = 53174
partitions(43) = 63261
partitions(44) = 75175
partitions(45) = 89134
partitions(46) = 105558
partitions(47) = 124754
partitions(48) = 147273
partitions(49) = 173525


#### Memoization

Caching intermediate values we can avoid a lot of recursive calls. For example, for $n = 49$ the algorithm is making $1836439$ calls. Of them $1834638$ can be avoided, having only $1801$ non-cached calls.

#### Time complexity

Since we are doing two recursive calls for each call, the algorithm is exponential in its non-memoized version, so it is no more than $O(2^n)$.

For the memoized version, since there are no more than $n^2$ distinct $(n, k)$ pairs that can feed the function numberOfPartitions, in that case the algorithm is $O(n^2)$.

#### An asymptotic formula

There is no known closed elementary formula known for numberOfPartitions(n), but Hardy and Ramanujan found, in 1918, its asymptotic behaviour:

$$p(n) \sim \frac{1}{4 n{\sqrt{3}}} \exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)$$