Sharing a working C++ solution


  • 2
    W
    • Traverse all transactions, record the debt situation of each person.
    • Do backtracking for each person. During each recursion, try to match this person's with every other person.
      I am sure this is not an optimal solution. But it seems this problem is NP-hard, and we can only do searching.
    class Solution {
    public:
        int minTransfers(vector<vector<int>>& transactions) {
            unordered_map<int, long> debts;
            for(auto& tup: transactions) {
                debts[tup[0]] -= (long)tup[2];
                debts[tup[1]] += (long)tup[2];
            }
            vector<int> arr;
            for(auto& p: debts) {
                if(p.second != 0) arr.push_back(p.second);
            }
            return helper(arr, 0, arr.size(), 0);
        }
        
    private:
        int helper(vector<int>& a, int start, int n, int num) {
            int ans = INT_MAX;
            while(start < n && a[start] == 0) start++;
            for (int i = start + 1; i < n; ++i) {
                if (a[i] < 0 && a[start] > 0 || a[i] > 0 && a[start] < 0) {
                    a[i] += a[start];
                    ans = min(ans, helper(a, start + 1, n, num + 1));
                    a[i] -= a[start];
                }
            }
            return ans == INT_MAX ? num : ans;
        }
    };
    

  • 0

    @wangxinbo Nice concise solution. An improvement could be made in the DFS loop

    for (int i = start + 1; i < n; ++i)

    where you could skip an index i if the same value a[i] has been tested before:

            for (int i = start + 1, prev = 0; i < n; ++i) {
                if (a[i] != prev && (a[i] < 0 && a[start] > 0 || a[i] > 0 && a[start] < 0)) {
                    a[i] += a[start];
                    ans = min(ans, helper(a, start + 1, n, num + 1));
                    prev = (a[i] -= a[start]);
                }
            }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.