下面的代码用于打印加法的组合。在打印时使用递归。思路来自于打印一个集合的所有子集;不过对于集合的所有子集,没有重复的情况。在打印加法组合的时候,因为有重复的情况的。这里处理重复是通过判断是否递减序列来实现的。即只保留有序序列即可实现。
?
递归结束后需要恢复现场
?
/**
?* 打印加法组合
?* 例如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--;
}
?
}
}