一道面试题

taige

求10000的可能的组合的个数
比如
1+9999
1+2+9997
1+2+3+9994
......
每个数都不一样，数的次序不考虑

比如5的可能组合的个数是2
1+4
2+3

用递归实现

taige

我做出来了，与大家分享

不过建议大家拿20、30作为输入运行
不然半天得不到结果

1. import java.util.*;
   
2. 
   
3. public class may {
   
4.         static long count = 0;
   
5.         static int number = 300;
   
6.         static Stack stack = new Stack();
   
7.    
   
8.         public static void main(String[] args) throws Exception {
   
9.                 if (args.length >; 0) {
   
10.                         number = Integer.parseInt(args[0]);
    
11.                 }
    
12.                 foo(number, 1);
    
13.                 System.out.println(number + ": " + count);
    
14.         }
    
15. 
    
16.         public static void foo(int n, int m) {
    
17.                 int s = 0;
    
18.                 if ((n%2) == 0) { //偶数
    
19.                         s = (n/2) - 1;
    
20.                 } else { //奇数
    
21.                         s = (n-1)/2;
    
22.                 }
    
23.                 for (int i = m; i <= s; i++) {
    
24.                         //stack.push(new Integer(i));
    
25.                         int c = n - i;
    
26.                         //System.out.print(number + " = ");
    
27.                         //for (int j = 0; j < stack.size(); j++) {
    
28.                         //        System.out.print((Integer)stack.elementAt(j) + " + ");
    
29.                         //}
    
30.                         //System.out.println(c);
    
31.                         count++;
    
32.                         foo(c, i+1);
    
33.                         //stack.pop();
    
34.                 }
    
35.         }
    
36. }

复制代码

晴天羽

如果是一万个1，算不算一个组合？

灰色轨迹

[quote]原帖由 "晴天羽"]如果是一万个1，算不算一个组合？[/quote 发表：


都说了不能重复了