465. Optimal Account Balancing

• Settling Multiple Debts Efficiently: An Invitation to Computing Science by T. Verhoeff, June 2003.

https://discuss.leetcode.com/topic/76158/11-liner-9ms-dfs-solution-detailed-explanation

class Solution {
public:
    int minTransfers(vector<vector<int>>& transactions) {
        unordered_map<int, int> tmp;
        for (auto t : transactions) 
            tmp[t[0]] += t[2], tmp[t[1]] -= t[2];
        for (auto t : tmp)
            if (t.second) debts.push_back(t.second);
        return DFS(0, 0); 
    }
private:
    vector<int> debts;
    int DFS(int k, int cnt) {//dealing with the kth debt, have done cnt transitions
        while (k < debts.size() && !debts[k]) k++;
        if (k == debts.size()) return cnt;
        int res = INT_MAX;
        for (int i = k + 1; i < debts.size(); i++)
            if (debts[i] != debts[i - 1] && debts[i] * debts[k] < 0) {
                debts[i] += debts[k];
                res = min(res, DFS(k + 1, cnt + 1));
                debts[i] -= debts[k];
            }
        return res;
    }
};