组合

描述 :

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

题目  :

LeetCode 77. 组合 :

77. 组合

分析 :

请看回溯怎么回事 , 里面讲的很清晰 .

解析 ;

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new ArrayList<>();
        if(n <= 0 || n < k){
            return list;
        }
        Deque<Integer> deque = new ArrayDeque<>();
        dfs(n,k,1,list,deque);
        return list;
    }
    //dfs 深度优先搜索的意思
    public void dfs (int n,int k,int start,List<List<Integer>> list,Deque<Integer> deque){
        if(deque.size() == k){
            list.add(new ArrayList<>(deque));
            return;
        }
        for(int i = start;i <= n;i++){
            deque.addLast(i);
            dfs(n,k,i + 1,list,deque);
            deque.removeLast();
        }
    }
}