Description

Any natural number $n$ greater than $1$ can be decomposed into a sum of several natural numbers that are each less than $n$. Given a natural number $n$, list all decompositions of $n$ into a sum of natural numbers, where every addend is less than $n$. In each decomposition, the numbers must be written in nondecreasing order. Then output these sequences in lexicographic order, with lexicographically smaller sequences printed first.

Input Format

Input: a single natural number $n$.

Output Format

Output: several addition expressions. Print one decomposition per line as $a_1+a_2+\dots+a_k$, where each $a_i$ is a natural number less than $n$, the sequence is in nondecreasing order, and the lines are sorted in lexicographic order.

7

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

Hint

Constraints: $2 \leq n \le 8$.

Translated by ChatGPT 5