465

class Solution {
public:
    int minAns = INT_MAX;
    int minTransfers(vector<vector<int>>& transactions) {
        unordered_map<int, int> m;
        for(auto t: transactions){
            m[t[1]] += t[2];
            m[t[0]] -= t[2];
        }
        vector<int> bal;
        for(auto p: m){
            if(p.second)
                bal.push_back(p.second);
        }
        int ans = 0, idx = 0;
        solve(bal, idx, ans);
        return minAns;
    }

    void solve(vector<int> &bal, int idx, int ans){
        if(idx == bal.size()){
            minAns = min(ans, minAns);
            return;
        }
        if(ans > minAns) return;
        if(bal[idx] == 0) solve(bal, idx+1, ans);
        for(int i=idx+1; i<bal.size(); i++){
            if(bal[i]*bal[idx] < 0){
                bal[i] += bal[idx];
                solve(bal, idx+1, ans+1);
                bal[i] -= bal[idx];
            }
        }
    }

};