# Sharing a working C++ solution

• 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;
}
};
``````

• @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]);
}
}
``````

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