1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows Hard

1/**
2 * [1439] Find the Kth Smallest Sum of a Matrix With Sorted Rows
3 *
4 * You are given an m x n matrix mat that has its rows sorted in non-decreasing order and an integer k.
5 * You are allowed to choose exactly one element from each row to form an array.
6 * Return the k^th smallest array sum among all possible arrays.
7 *  
8 * Example 1:
9 * 
10 * Input: mat = [[1,3,11],[2,4,6]], k = 5
11 * Output: 7
12 * Explanation: Choosing one element from each row, the first k smallest sum are:
13 * [1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.
14 * 
15 * Example 2:
16 * 
17 * Input: mat = [[1,3,11],[2,4,6]], k = 9
18 * Output: 17
19 * 
20 * Example 3:
21 * 
22 * Input: mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
23 * Output: 9
24 * Explanation: Choosing one element from each row, the first k smallest sum are:
25 * [1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.  
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	m == mat.length
31 * 	n == mat.length[i]
32 * 	1 <= m, n <= 40
33 * 	1 <= mat[i][j] <= 5000
34 * 	1 <= k <= min(200, n^m)
35 * 	mat[i] is a non-decreasing array.
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/
41// discuss: https://leetcode.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn kth_smallest(mat: Vec<Vec<i32>>, k: i32) -> i32 {
47        0
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_1439() {
59    }
60}
61