中兴面试题 ： 输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数, 使其和等于 m. --java算法解决方法。

2010年中兴面试题 编程求解： 输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数, 使其和等于 m ,要求将其中所有的可能组合列出来.

 

看了一下网络上基本都是C++的答案，这和中兴招人的要求有关，不过我是学java的，给一个java的算法：

 

主要思路是排列组合，然后把组合中符合条件的都过滤出来：

 

public class CombinationToSum {     public static void main(String[] args) {         permutation(6, 6);     }     private static void permutation(int sum, int n) {                 for(int i=n; i>0; i--){             if(i == sum){                 System.out.println(i);                 continue;             }             int pos = i - 1;             while(pos > 0){                 List<Integer> ls = new ArrayList<Integer>();                 ls.add(i);                 for(int j=pos; j>0; j--){                     int ret = judge(ls, j, sum);                     if(ret < 0){                         ls.add(j);                     }                     if(ret == 0){                         ls.add(j);                         for(int k=0; k<ls.size(); k++){                             System.out.print(ls.get(k) + " ");                         }                         System.out.println();                         pos = ls.get(1) - 1;                         break;                     }                     pos = 0;                 }             }         }             }     private static int judge(List<Integer> ls, int num, int sum){         int result = 0;         int total = 0;         for(Integer i: ls){             total += i;         }         total += num;         if(total > sum){             result = 1;         }         if(total < sum){             result = -1;         }         return result;     } }

 

输入6， 6

输出：

6 5 1 4 2 3 2 1

输入10， 10

输出：

10 9 1 8 2 7 3 7 2 1 6 4 6 3 1 5 4 1 5 3 2 4 3 2 1

 

大家可以试一下，如果以前没有做过排列组合，中兴出的题还是挺有难度的。