#P1500. 数的拆分

    ID: 491 传统题 1000ms 128MiB 尝试: 3 已通过: 2 难度: 10 上传者: 标签>搜索与回溯搜索信息学奥赛一本通玄级

数的拆分

Description

任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和。当n=7,共有14种拆分方法:

Input Format

输入1行:整数n。

Output Format

输出多行:每一行表示一种拆分方案,最后一行输出方案总数。

7

7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
14

Hint


Source

搜索与回溯 搜索 信息学奥赛一本通 玄级