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 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