nikunjsoni

465

Jul 13th, 2021
110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int minAns = INT_MAX;
  4.     int minTransfers(vector<vector<int>>& transactions) {
  5.         unordered_map<int, int> m;
  6.         for(auto t: transactions){
  7.             m[t[1]] += t[2];
  8.             m[t[0]] -= t[2];
  9.         }
  10.         vector<int> bal;
  11.         for(auto p: m){
  12.             if(p.second)
  13.                 bal.push_back(p.second);
  14.         }
  15.         int ans = 0, idx = 0;
  16.         solve(bal, idx, ans);
  17.         return minAns;
  18.     }
  19.    
  20.     void solve(vector<int> &bal, int idx, int ans){
  21.         if(idx == bal.size()){
  22.             minAns = min(ans, minAns);
  23.             return;
  24.         }
  25.         if(ans > minAns) return;
  26.         if(bal[idx] == 0) solve(bal, idx+1, ans);
  27.         for(int i=idx+1; i<bal.size(); i++){
  28.             if(bal[i]*bal[idx] < 0){
  29.                 bal[i] += bal[idx];
  30.                 solve(bal, idx+1, ans+1);
  31.                 bal[i] -= bal[idx];
  32.             }
  33.         }
  34.     }
  35.    
  36. };
RAW Paste Data