java递归实现一acm题

miman2008

题目要求：
求满足从1开始，某一整数以内的数组合相加等于其本身的各种情况
例如：整数20，求组合相加等于20的情况：
 1 19
 1 2 17
 1 2 3 14
 1 2 3 4 10
 1 2 3 5 9
 1 2 3 6 8 
 1 2 4 13
 .
 .
 .
 7 13 
 8 12 
 9 11
 
不能重复，交换顺序视为同一种情况。
package alibaba;import java.util.HashSet;import java.util.Scanner;import java.util.Set;public class combination {static int count = 0;public static  void combine(int index,int sum,Set<Integer> set){    if(set== null){     set = new HashSet<Integer>();    }if( index  < sum/2){//递归入口，sum如果能分成两个比index都大的数则进行递归，否则此轮递归结束，回溯继续运行。int i = index + 1;int temp = 0;set.add(index);if(sum%2  ==  0){temp = sum /2;}else temp = sum/2 +1;count++;System.out.print(count+": ");    for (Integer integer : set) {System.out.print(integer+" ");}    System.out.println(sum);   for(;i<temp;i++){//temp为中间值，循环变量无法到达这一值，避免重复情况set.add(i);combine(i, sum-i,set);set.remove(i);} }else{set.add(index);set.add(sum);count++;System.out.print(count+": ");for (Integer integer : set) {System.out.print(integer+" ");}System.out.println();set.remove(index);set.remove(sum);}}public static void main(String[] args) {Scanner  scanner  = new Scanner(System.in);System.out.println("请输入两个整数");int index = scanner.nextInt();int sum = scanner.nextInt();for(int i=index; i <sum/2; i ++){          combine(i,sum-i,null);}System.out.println("方案总数为："+count);}} 
输出结果：
请输入两个整数
1
20
1: 1 19
2: 1 2 17
3: 1 2 3 14
4: 1 2 3 4 10
5: 1 2 3 5 9
6: 1 2 3 6 8
7: 1 2 4 13
8: 1 2 4 5 8
9: 1 2 4 6 7
10: 1 2 5 12
11: 1 2 6 11
12: 1 2 7 10
13: 1 2 8 9
14: 1 3 16
15: 1 3 4 12
16: 1 3 4 5 7
17: 1 3 5 11
18: 1 3 6 10
19: 1 3 7 9
20: 1 4 15
21: 1 4 5 10
22: 1 4 6 9
23: 1 4 7 8
24: 1 5 14
25: 1 5 6 8
26: 1 6 13
27: 1 7 12
28: 1 8 11
29: 1 9 10
30: 2 18
31: 2 3 15
32: 2 3 4 11
33: 2 3 4 5 6
34: 2 3 5 10
35: 2 3 6 9
36: 2 3 7 8
37: 2 4 14
38: 2 4 5 9
39: 2 4 6 8
40: 2 5 13
41: 2 5 6 7
42: 2 6 12
43: 2 7 11
44: 2 8 10
45: 3 17
46: 3 4 13
47: 3 4 5 8
48: 3 4 6 7
49: 3 5 12
50: 3 6 11
51: 3 7 10
52: 3 8 9
53: 4 16
54: 4 5 11
55: 4 6 10
56: 4 7 9
57: 5 15
58: 5 6 9
59: 5 7 8
60: 6 14
61: 7 13
62: 8 12
63: 9 11
方案总数为：63