Untitled

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 {};
    }
};