有序矩阵中的第 k 个最小数组和

题目
给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。

你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。

二分+dfs，很神奇的想法

#include<iostream>
#include<string>
#include<deque>
#include<cmath>
#include<vector>
#include<unordered_map>
#include<utility>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int rowLength=0,colLength=0,kth=0,cnt=1; 
void dfs(int row,int sum,int target,vector<vector<int>>& mat) {
    
	//出口条件 
	if (sum > target || cnt > kth || row >= rowLength) return;
	//第一列值之和 
	dfs(row+1,sum,target,mat);
	//不同列之和 
	for(int i=1; i<colLength; i++) {
    
		int curSum=sum-mat[row][0]+mat[row][i];
		if (curSum > target) break;
		cnt++;
		dfs(row + 1, curSum, target,mat);
	}
}

int kthSmallest(vector<vector<int>>& mat, int k) {
    
	rowLength=mat.size(),colLength=mat[0].size(),kth=k;
	//二分搜索头尾范围 
	int left = 0, right = 0;
	for (int i = 0; i < rowLength; i++) {
    
		left += mat[i][0];
		right += mat[i][colLength - 1];
	}
	right++;
	int init=left;
	cout<<" left "<<left<<" right"<<right<<endl;
	while(left<right) {
    
		int mid=left+(right-left)/2;
		cnt=1;
		//行号 初始最小和 中间值 矩阵 
		dfs(0,init,mid,mat);
		if(cnt<k) {
    
			left=mid+1;
		} else {
    
			right=mid;
		}
		// cout<<"cnt "<<cnt<<" right"<<right<<endl;
	}
	return left;
}
int main()
{
    
    int m, n,data,k;
    vector<vector<int> > mat;
    cin>>m>>n;
    for(int i=0; i<m; i++)
    {
    

        vector<int> row;
        for(int j=0; j<n; j++)
        {
    
            cin>>data;
            row.push_back(data);
        }
        mat.push_back(row);
    }
    cin>>k;
    int res=kthSmallest(mat,k);
    cout<<res<<endl;
    return 0;

}