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

1.Problem
https://leetcode.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/

2.Idea
Divide & Conquer. Process by 2 rows from top.

3.Source

 class Solution {  
 public:  
      int kthSmallest(vector<vector<int>>& mat, int k) {  
           vector<int> ans = mat[0];  
           int n = mat.size();  
           int m = mat[0].size();  
           for (int i = 1; i < n; i++) {  
                vector<int> tmp;  
                for (int j = 0; j < ans.size(); j++) {  
                     for (int l = 0; l < m; l++) {  
                          tmp.push_back(ans[j] + mat[i][l]);  
                     }  
                }  
                sort(tmp.begin(), tmp.end());  
                ans.clear();  
                for (int i = 0; i < min(k, (int)tmp.size()); i++) {  
         ans.push_back(tmp[i]);  
       }  
           }  
           return ans[k - 1];  
      }  
 };