77. 组合

class Solution {
    private Integer n;
    private List<Integer> chosen = new ArrayList<>();
    private List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        //注意这个题意是从1开始的
        recur(1,k);
        return result;
    }
    public void recur(int cur,int k){
        //0 : 剪枝。减去子树多余的枝丫。如果当前chosen已经 > k了，或者chosen + 剩余的n 长度已经不满足k了就可以提前返回
        if(chosen.size() > k || chosen.size() + (n - cur + 1) < k){
            return;
        }
        //1:递归结束条件,只要chosen的长度==k就结束了。
        //为什么不用考虑cur > n的情况呢，因为上面的剪枝操作已经给减掉了，不用考虑了。
        //递归结束条件一定要想清楚。78题不包含n是因为当前内个cur是代表下标所以只到n-1
        if(chosen.size() == k){
            //这块要想清楚
            result.add(new ArrayList<>(chosen));
            return;  
        }
        //2:递归方法，相似的方法
        //如果不要这个当前数就直接往下走
        recur(cur + 1,k);
        //如果要这个数，就把cur存到chosen里面然后再往下走
        chosen.add(cur);
        recur(cur + 1,k);
        //3:还原现场，把当前这一层加入的数弹出来
        chosen.remove(chosen.size()-1);
    }
}