中兴面试题：输入两个整数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 ls = new ArrayList();
                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                            System.out.print(ls.get(k) + " ");
                        }
                        System.out.println();
                        pos = ls.get(1) - 1;
                        break;
                    }
                    pos = 0;
                }
            }
        }
       
    }
    private static int judge(List 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             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

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