day-47 组合

思路
回溯：利用个dfs方法递归调用，每个元素有选或不选两种抉择，当选中元素个数等于k时，将链表p加入答案，当ids==n且选中元素个数小于n时，直接返回

解题过程
每次选中元素调用dfs方法后记得还原

Code

class Solution {
    public List<List<Integer>> list =new ArrayList<>();
    public int nn;
    public int kk;
    public List<List<Integer>> combine(int n, int k) {
        List<Integer> p=new ArrayList<>();
        nn=n;
        kk=k;
        dfs(p,0,0);
        return list;
    }
    public void dfs(List<Integer> p,int ids,int num){
        if(num==kk){
            list.add(new ArrayList(p));
            return;
        }
        if(ids==nn) return;
        dfs(p,ids+1,num);
        
        p.add(ids+1);
        dfs(p,ids+1,num+1);
        p.remove(p.size()-1);
    }
}

作者：菜卷
链接：https://leetcode.cn/problems/combinations/solutions/2902088/zu-he-by-ashi-jian-chong-dan-liao-shi-ya-bwh6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。