lintcode：数字组合III

数字组合III

组给出两个整数n和k，返回从1......n中选出的k个数的组合。

您在真实的面试中是否遇到过这个题？

Yes

样例

例如 n = 4 且 k = 2

返回的解为：

[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]] 

解题

数字组合I  数组组合II

同样式DFS

本题只需要增加判断size 是否等于k的情况

public class Solution {

    /**

     * @param n: Given the range of numbers

     * @param k: Given the numbers of combinations

     * @return: All the combinations of k numbers out of 1..n

     */

    public ArrayList<ArrayList<Integer>> combine(int n, int k) {

        // write your code here

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        if(n<0 || k<0)

            return result;

        int start = 1;

        ArrayList<Integer> list = new ArrayList<Integer>();

        DFS(n,k,start,result,list);

        return result;

    }

    public void DFS(int n,int k,int start ,ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list){

        if(list.size() == k){

            ArrayList<Integer> tmp = new ArrayList<Integer>(list);

            if(!result.contains(tmp)) // 可不要

                result.add(tmp);

            return;

        }

        for(int i = start;i<=n ;i++){

            list.add(i);

            DFS(n,k,i+1,result,list);

            list.remove(list.size() -1);

        }

    }

}

lintcode：数字组合III的相关教程结束。