Leetcode 465

Leetcode 465 Optimal Account Balancing

题目意思：一堆人互相转账，互有借贷，现在问要多少次重新转账才能让大家 互不相欠。

代码：dfs

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

    int helper(vector<int>& debts,int pos,int count){
        while(pos<debts.size() && debts[pos]==0) pos++;
        if(pos>=debts.size()) return count;
        int res = INT_MAX;
        for(int i= pos+1;i<debts.size();i++){
            if((debts[pos] ^ debts[i])<0){
                debts[i]+=debts[pos];
                res = min(res,helper(debts,pos+1,count+1));
                debts[i]-=debts[pos];
            }
        }
        return res;
    }
};