代码随想录算法训练营day24 | leetcode 77. 组合

基础知识

回溯法解决的问题都可以抽象为树形结构，集合的大小就构成了树的宽度，递归的深度构成的树的深度

void backtracking(参数) {

    if (终止条件) {

        存放结果;

        return;

    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {

        处理节点;

        backtracking(路径，选择列表); // 递归

        回溯，撤销处理结果

    }

}

LeetCode 77. 组合

分析1.0

class Solution {

    List<List<Integer>> res = new ArrayList();

    LinkedList<Integer> path = new LinkedList();

    public List<List<Integer>> combine(int n, int k) {

        backTracking(n, k, 1);

        return res;

    }

    // 模拟人脑

    public void backTracking(int n, int k, int start){

        if(path.size() == k){

            //res.add(path);

            res.add(new LinkedList(path));

            return;

        }

        // 剪枝优化

        for(int i = start; i <= n-(k-path.size())+1; i++){

            path.add(i);

            // backTracking(n, k, start++); 有状态 会持续作用

            backTracking(n, k, i+1);

            path.removeLast();

        }

    }

}

总结

path始终在变化，要将某一刻的状态保留下去只能把path赋值给另一个容器
参数++会改变状态 而单纯+1仅仅意味着某个数

常用变量名增量更新

size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag、ch、path

代码随想录算法训练营day24 | leetcode 77. 组合的相关教程结束。