Untitled
unknown
plain_text
a year ago
1.1 kB
8
Indexable
class Solution { public: vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) { vector<vector<int>> ans; for (int &r : rowSum) { vector<int> rowAns; ans.emplace_back(dfs(r, rowSum.size(), colSum, 0, rowAns).first); } return ans; } pair<vector<int>, bool> dfs(int sum, int rowSize, vector<int>& colSum, int colIdx, vector<int> &ans) { if (colIdx == colSum.size() && sum == 0) { return pair{ans, true}; } if (sum != 0 && colIdx == colSum.size()) { return pair{ans, false}; } for (int i=0; ; ++i) { int element = min(colSum[colIdx], sum) - i; if (element < 0) break; ans.emplace_back(element); colSum[colIdx] -= element; pair<vector<int>, bool> tmpAns = dfs(sum - element, rowSize, colSum, colIdx + 1, ans); if (tmpAns.second) { return tmpAns; } else ans.pop_back(); colSum[colIdx] += element; } return {}; } };
Editor is loading...
Leave a Comment