黑马程序员技术交流社区

标题: 求一个整数的所有相加组合情况 [打印本页]

---

作者: ooyeah    时间: 2015-8-18 00:59
标题: 求一个整数的所有相加组合情况
从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

---

作者: leiyingyin    时间: 2015-8-18 00:59

1. import java.util.HashSet;
   
2. import java.util.Scanner;
   
3. import java.util.Set;
   
4. 
   
5. 
   
6. class combination {
   
7.         static int count = 0;
   
8.         public static  void combine(int index,int sum,Set<Integer> set){
   
9.             if(set== null){
   
10.                      set = new HashSet<Integer>();
    
11.             }
    
12.                 if( index  < sum/2){//递归入口，sum如果能分成两个比index都大的数则进行递归，否则此轮递归结束，回溯继续运行。
    
13.                 int i = index + 1;
    
14.                 int temp = 0;
    
15.                 set.add(index);
    
16.                 if(sum%2  ==  0){
    
17.                         temp = sum /2;
    
18.                 }else temp = sum/2 +1;
    
19.                 count++;
    
20.                 System.out.print(count+": ");
    
21.             for (Integer integer : set) {
    
22.                         System.out.print(integer+" ");
    
23.                 }
    
24.             System.out.println(sum);
    
25.           
    
26.                 for(;i<temp;i++){//temp为中间值，循环变量无法到达这一值，避免重复情况
    
27.                         set.add(i);
    
28.                         combine(i, sum-i,set);
    
29.                         set.remove(i);
    
30.                 }
    
31.          }
    
32.         else{
    
33.                 set.add(index);
    
34.                 set.add(sum);
    
35.                 count++;
    
36.                 System.out.print(count+": ");
    
37.                 for (Integer integer : set) {
    
38.                         System.out.print(integer+" ");                       
    
39.                 }
    
40.                 System.out.println();
    
41.                
    
42.                 set.remove(index);
    
43.                 set.remove(sum);
    
44.         }
    
45.                
    
46.         }
    
47.         public static void main(String[] args) {
    
48.                 int num = 20;
    
49.                 for(int i=1; i <num/2; i ++){
    
50.           combine(i,num-i,null);
    
51.                 }
    
52.         }
    
53. 
    
54. }
    

复制代码

应该没问题吧，好困，睡觉去。。。。

---

作者: leiyingyin    时间: 2015-8-18 01:24
完美解决！！！我再测试下哈

---

作者: liuch111    时间: 2015-8-18 20:01

leiyingyin 发表于 2015-8-18 01:32
应该没问题吧，好困，睡觉去。。。。

写的不错 多点注释更好

---

作者: ooyeah    时间: 2015-8-18 22:19
撸得一手好代码~~~

---

作者: JOKER0819    时间: 2015-8-28 22:45

leiyingyin 发表于 2015-8-18 00:59
应该没问题吧，好困，睡觉去。。。。

数学很好啊！我一做算法题就头疼。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2