网站建设 体会友情链接系统

题目传送门
主要看灵神的二分模版，如何使用递归实现在$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) // 能递归到这里，说明数组和不超过二分的 midreturn --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) >= kint 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) < kleft = 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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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