算法练习第二十四天|77. 组合

77. 组合

class Solution {
    List<List<Integer>> result = new ArrayList();
    List<Integer> path = new ArrayList();
    public List<List<Integer>> combine(int n, int k) {
        backtrace(n,k,1);
        return result;
    }

    public void backtrace(int n,int k,int startIndex){
        //终止条件
        if(path.size() == k){
            //存放结果
            result.add(new ArrayList<>(path));
            return;
        }
        //遍历树的一层每个节点
        //这里做剪枝操作
        //k-path.size() == 剩余需要往这个数组里面增加的的元素个数、
        //n-(k-path.size()) + 1 == 最大的起始位置，+1是包含起始位置
        //for(int i = startIndex;i<=n;i++){
        for(int i = startIndex;i<=n-(k-path.size()) + 1;i++){
            path.add(i);
            backtrace(n,k,i+1);
            //回溯，撤销处理结果
            path.removeLast();
        }

    }
}