Partições de um número natural

Crie uma função que determine o número de partições de um número natural.

Uma partição de um número n é uma soma não ordenada de um ou mais números cujo total é n. Por exemplo, as partições do número 4 são:

1 + 1 + 1 + 1 = 4
1 + 1 + 2 = 4
1 + 3 = 4
2 + 2 = 4
4 = 4

Como as partições não têm ordem, as somas 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = 4 são consideradas a mesma partição.

Exemplos

partitions(4) ➞ 5

partitions(10) ➞ 42

partitions(0) ➞ 1

partitions(1) ➞ 1

partitions(2) ➞ 2

Notas

Lembre-se da partição trivial n = n. Além disso, dizemos que há uma maneira de particionar zero; ou seja, 0 = 0.