SSOJ2364自然数的拆分问题
4850+
作者：crxis 发布：2017-07-28 分类：深度优先搜索
题目大意：任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和，请把所有拆分方案输出来。
输入
输入一个自然数n(1<n<10)
输出
输出不同的拆分方法，每一种拆分方法输出到一行。
样例输入
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
解题思路
按照“格子填数”的思想，一个一个填数字，与前面几道题不同的是，自然数拆分的格子数是不固定的，什么时候才结束递归呢？不能再划分下去的时候！
搜索时记录两个参数，一个是k，表示填到第k个格子；一个是s，表示剩余多少需要划分。先确定每个格子填数的范围——不比前一个数小，最大为s。当前格子确定数字i后，搜索下一个格子k+1，且修改剩余划分数字为s-i。最后考虑特殊情况，如k=2时没划分，输出时注意加号个数和换行等等。
程序实现
