77.组合

思路

先取1 对应三种情况
取2的时候 只能在3 4 中取下一个数
最后整体结构如图

这个树有几个孩子节点并不固定，每次递减，还是可以使用回溯方法来使用

code

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    //求解C(n,k) 当前已经找到的组合存储在c中，需要从start开始搜索新的元素
    private void generateCombinations(int n,int k,int start,LinkedList<Integer> c){
        //如果找到含有k个元素的集合 则添加到res中
        if(c.size()==k){
            res.add((LinkedList<Integer>)c.clone());
            return;
        }
        //从start开始搜索
        for(int i=start;i<=n;i++){
            //将当前遍历的元素加上c中
            c.addLast(i);
            //递归调用新的元素 i+1
            generateCombinations(n,k,i+1,c);
            //递归结束的时候将之前的元素出队
            c.removeLast();
        }
        return;
    }
    public List<List<Integer>> combine(int n, int k) {
        //判断边界条件
        if(n<=0||k<=0||k>n)
            return res;
        //start从1开始 传入一个c
        generateCombinations(n,k,1,new LinkedList<Integer>());
        return res;
    }
}