代码随想录算法训练营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();
        }
    }
}

总结

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

常用变量名增量更新

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