回溯递归的剪枝模版_灵神 模板

题目传送门
主要看灵神的二分模版，如何使用递归实现在$O(mk)$时间内，实现对于二分中每个条件的判断。
一般套路：

dfs函数返回值为布尔类型

循环中使用一个dfs，如果其返回true，那么直接这个dfs返回true

技巧：
一个引用类型的值作为终止条件的判断，所有的dfs共享这个变量。
灵神代码：

class Solution {
    // 返回是否找到 k 个子数组和
    bool dfs(vector<vector<int>> &mat, int &left_k, int i, int s) {
        if (i < 0) // 能递归到这里，说明数组和不超过二分的 mid
            return --left_k == 0; // 是否找到 k 个
        for (int x: mat[i]) { // 「枚举选哪个」，注意 mat[i] 是有序的
            if (x - mat[i][0] > s) // 选 x 不选 mat[i][0]
                break; // 剪枝：后面的元素更大，无需枚举
            if (dfs(mat, left_k, i - 1, s - (x - mat[i][0]))) // 选 x 不选 mat[i][0]
                return true; // 找到 k 个就一直返回 true，不再递归
        }
        return false;
    }

public:
    int kthSmallest(vector<vector<int>> &mat, int k) {
        int sl = 0, sr = 0;
        for (auto &row: mat) {
            sl += row[0];
            sr += row.back();
        }
        // 二分模板 https://www.bilibili.com/video/BV1AP41137w7/
        int left = sl - 1, right = sr; // 开区间 (sl-1,sr)
        while (left + 1 < right) { // 开区间不为空
            // 循环不变量：
            // f(left) < k
            // f(right) >= k
            int mid = left + (right - left) / 2;
            int left_k = k;
            if (dfs(mat, left_k, mat.size() - 1, mid - sl)) // 先把第一列的所有数都选上
                right = mid; // 二分范围缩小至开区间 (left, mid)
            else // f(mid) < k
                left = mid; // 二分范围缩小至开区间 (mid, right)
        }
        return right;
    }
};

作者：灵茶山艾府
链接：https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/solutions/2286593/san-chong-suan-fa-bao-li-er-fen-da-an-du-k1vd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

时间复杂度思考：
为什么回溯的时间复杂度为$O(mk)$，dfs递归的过程是一棵树从顶到底，本题中如果能够递归到$i<0$，那么就是走完了一条路径，该路径花费时间$O(mk)$。如果能够成功走完k条路径，那么就直接所有的dfs开始统一返回true，在此之前所有的dfs返回的都是false。
这样做的好处是，虽然每个dfs中的for循环还没结束，但是由于出现了一个true,提前终止了循环，所有就可以保证递归树中每一层的节点个数最多为k个。着实神奇，而且写法十分优雅！