对力扣77组合优化的剪枝操作的理解

77. 组合

代码随想录放出了这一张图

我乍一看觉得想当然,但是仔细想想,又不知道以下剪枝代码作何解释,因此我想通过这篇文章简要解释一下

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 剪枝的地方
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1);
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};

for循环里的"i <= n - (k - path.size()) + 1;"就是令人疑惑的地方,我的解释如下:

i是当前取何值,该限制条件就是i在当前所能取的值,既然i能在这取值,我们必须要保证下面的递归嵌套里面的for循环也能取到值(即基于该栈的后面的递归嵌套只能在i之后取值,我们要保证在这之后到n之间有足够的值保证path.size() == k),也就是说当下取值 i 后,所剩下能取的值必须满足path.size() == k这个条件.

因此当下i的可取范围应是能满足后面所有递归都能取值的前提下所能取的范围

在取当下的i值前,path还差k - path.size()个值才能满足path.size() == k,因为在[1,n]取值,那么这最后k - path.size()个值就必须不能超过[n - (k - path.size()) + 1, n],即n的后k - path.size()个值,因为i当前取值超过n - (k - path.size()) + 1后,后面的递归总有i无法取到值.

碎碎念:

泡图书馆也600个小时了,感觉自己的学习效率也慢慢好起来了,也能坚持每天8-10个小时学习了,我想对自己说一句:再接再厉!!未来可期!