465.txt

A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]].

Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.

Note:

A transaction will be given as a tuple (x, y, z). Note that x ≠ y and z > 0.
Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.
Example 1:

Input:
[[0,1,10], [2,0,5]]

Output:
2

Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.

Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.
Example 2:

Input:
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

Output:
1

Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.

Therefore, person #1 only need to give person #0 $4, and all debt is settled.









class Solution {
public:
    unordered_map<int,int>hash;
    vector<int>pos;
    vector<int>neg;
    int res=INT_MAX;
    int minTransfers(vector<vector<int>>& A) {
        for(vector<int>&p:A){
            int v1=p[0],v2=p[1],w=p[2];
            hash[v1]-=w;
            hash[v2]+=w;
        }
        
        for(auto it=hash.begin();it!=hash.end();it++){
            int v=it->first;
            int w=it->second;
            if(w<0){
                neg.push_back(-w);
            }
            if(w>0){
                pos.push_back(w);
            }
        }
       
        dfs(pos,neg,0,0,0);
        return res;
    }
    
    void dfs(vector<int>&pos,vector<int>&neg,int nindex,int pindex,int cnt){
        if(pindex>=pos.size()){
            int sum=0;
            for(int i:pos)sum+=i;
            if(sum==0){
                res=min(res,cnt);
            }
            return;
        }
        
        for(int i=nindex;i<neg.size();i++){
            if(neg[i]==0)continue;
            int old=neg[i];
            if(pos[pindex]<=neg[i]){
                int o=pos[pindex];
                pos[pindex]=0;
                neg[i]-=o;
                dfs(pos,neg,0,pindex+1,cnt+1);
                neg[i]+=o;
                pos[pindex]+=o;
                
            }
            else{
                pos[pindex]-=old;
                neg[i]=0;
                dfs(pos,neg,nindex+1,pindex,cnt+1);
                neg[i]=old;
                pos[pindex]+=old;
            }
        }
        
    }
    
};