回溯法 | 含有k个元素的集合

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(1,n,k, new ArrayList<>());
        return res;
    }
    public void dfs(int q, int n, int k, List<Integer> list){
        if( (n-q+1) < (k-list.size())) return;
        if(list.size()==k){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i=q;i<=n;i++){
            list.add(i);
            dfs(i+1,n,k,list);
            list.remove(list.size()-1);
        }
    }
}