网上的多种解法比较复杂，本文用递归方法，22行代码搞定。时间和空间复杂度已经降到最低！
第三版：加入创作思路。
这个函数的主要功能就是输出所有组合。既然是输出所有的组合，那就意味着内部有一个遍历所有组合的过程。既然是遍历，而且是O(N)时间，那就说明这个遍历是按照某种输出次序，从“第一个组合”遍历到“最后一个组合”。
如何给组合定义次序呢？举例说明
例1:
3=1+1+1
3=1+2
3=3
上面的例子就说明了次序，即，按照组合中出现数字的从小到大顺序。
定义了次序，剩下的就是如何让程序按照这个程序一个一个的遍历。遍历的过程不会那么完美的一个不重复，当然也会重复，这就涉及到过滤。过滤那些重复的元素，举例说明
例2:
3=1+1+1
3=1+2
3=2+1
3=3
可以看出这个例2中的3=2+1被过滤掉了，并没有输出，这也是必须的，为什么呢？因为3=2+1和之前出现的3=1+2本质上就是一种组合，还要交换一下数字的位置就可以了。而加法自然有交换率。所以就不必输出了。从这里还可以看出来过滤的依据，那就是让一个组合中的所有数字也保持从小到大出现，这样就不会出现3=2+1了，因为2比1大，之前肯定出现过了。这样一来就解决了输出的唯一性
至此，就剩下如递归的进行了。递归的思路是这样的，例如拆分3:
既然
3=1+后续组合
那么递归也就自然的变成了对“后续组合”进行继续拆分，只要“后续组合“的所有排列找到了，后续组合的每个排列前面加上1这个前缀自然就解决了1作为前缀的所有情况，这样一来就会遍历到
3=1+1+1
3=1+2
由于组合次序的定义可以知道，1作为前缀的情况被遍历完之后，自然就变成了遍历2开头的数字
2开头的数字还需要遍历吗？基于如下事实
n=m1+m2+...+mk, m1<m2<...<mk
第一个数字m1不会超过n/2，因为m1后面的数字要比m1大。所以可以看出，遍历的时候第一个数字最多尝试到n/2.
但是m1最大取n/2是合理的，比如
11=5+6
也就是说拆分的时候总是有拆分成两个数的和的形式，其中n=m1+m2,m1<m2，这样一来m1取n/2就是合适的。
那么下面就是递归程序的实现了。
f(int n,list l,int start)
参数说明：
n:这里n表示要对n进行拆分
l:这里表示子拆分的时候前缀的那些子递增序列，当n被初次拆分的时候，list当然是空的，只有子拆分才会有非空的前缀
start：表示在遍历的时候当前组合的第一个数字，这个数字用来去除重复，参考输出的唯一性
java实现:
public class Sum1ToN {
private void print(List<Integer> list) {
for (Integer k : list) {
System.out.print(k + "+");
}
}
private void f(int n, List<Integer> list, int start) {
if (n == 1) {
print(list);
System.out.println(1);
} else {
for (int i = start; i <=n / 2; i++) {
list.add(i);
f(n - i, list, i);
list.remove(list.size() -1);
}
print(list);
System.out.println(n);
}
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
new Sum1ToN().f(9,list, 1);
}
}
输出：f(9,null,1)
京公网安备 11010502036488号