java递归实现一acm题
题目要求：求满足从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 staticvoid 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) {Scannerscanner= 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
页:
[1]