Gegeven is een positief geheel getal \(k\). Gevraagd is om alle manieren te bepalen om \(k\) te vormen als een som van positieve gehele getallen. Bijvoorbeeld, 3 kan gevormd worden als \(3, 2+1, 1+1+1\).

Opgave

Schrijf een Python-functie partition(n:int) die voor een gegeven getal alle manieren teruggeeft om dat getal te vormen. De uitvoer moet als volgt gesorteerd zijn:

• Elke mogelijkheid moet inwendig gesorteerd zijn van groot naar klein
• De overkoepelende lijst van mogelijkheden moet lexicografisch gesorteerd zijn, dit wil zeggen: [1,1,1,1] < [2,1,1] < [2,2] < [3,1] < [4]

Voorbeeld

>>> partition(4)
[[1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]]