自然数的拆分问题(Number Partition)

题目描述

将自然数 n 拆分为若干个小于 n 的自然数之和（至少拆成两个数），求所有的拆分方案。

为避免重复（例如 1+3 和 3+1 视为同一种拆分），要求每种方案中的加数按非降序排列，即后面拆分出的数不小于前面拆分出的数。

输入格式

一行一个整数 n。

输出格式

每行一种拆分方案，形如 a+b+...，加数之间用 + 连接。按加数非降序、字典序输出。若没有任何拆分方案，则不输出任何内容。

样例输入

5

样例输出

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

数据范围

1 ≤ n ≤ 20。