打印一个数的加法组合

下面的代码用于打印加法的组合。在打印时使用递归。思路来自于打印一个集合的所有子集；不过对于集合的所有子集，没有重复的情况。在打印加法组合的时候，因为有重复的情况的。这里处理重复是通过判断是否递减序列来实现的。即只保留有序序列即可实现。

?

递归结束后需要恢复现场

?

/**

?* 打印加法组合

?* 例如5可以输出：

?* ?5?

4 1?

3 2?

3 1 1?

2 2 1?

2 1 1 1?

1 1 1 1 1?

?* 下面的代码使用了递归!

?* 在去重上，采用的是判断数组的顺序是不是按照降序排列的，如果是的话，则是符合条件的。否则不符合条件跳出；?

?* 本程序的核心递归要点是：?

?* 1. 申请一个数组给递归使用；?

?* 2. 递归代码在使用数组后需要恢复原状；?

?* 3. 递归的时机；

?*?

?* @author ajwang

?*

?*/

public class Main {

?

public static void main(String[] args) {

int[] array = new int[5];

print(5, array, -1);

?

}

?

public static void print(int n, int[] array, int end) {?

?

//在n=1,n=0时，表明array里面已经保存了所有要打印的数字了。这时候就可以开始打印，不过考虑到重复的情况，如果不是递减的就不输出；

if (n == 0) {?

for (int i = 1; i <= end; i++) {

if(array[i-1]<array[i]){

return ;

}

}

for (int i = 0; i <= end; i++) {

System.out.print(array[i] + " ");

}

System.out.println();

return;

}

if (n == 1) {

?

array[++end] = 1;

for (int i = 1; i <= end; i++) {

if(array[i-1]<array[i]){

return ;

}

}

for (int i = 0; i <= end; i++) {

System.out.print(array[i] + " ");

}

System.out.println();

return;

}

//核心的递归循环代码，对于N>1的情况，分别对end的各种情况进行赋值，直到变为0；

for (int i = n; i > 0; i--) {

array[++end] = i;

print(n - i, array, end);

end--;

}

?

}

}