MY AC code

• I am not sure whether my code is correct....
The complexity is O(2^N) I think.

``````import java.util.*;

public class Solution {
private int ans = Integer.MAX_VALUE;

public int minTransfers(int[][] transactions) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int[] x : transactions) {
if (!map.containsKey(x[0]))
map.put(x[0], -x[2]);
else
map.put(x[0], map.get(x[0])-x[2]);

if (!map.containsKey(x[1]))
map.put(x[1], x[2]);
else
map.put(x[1], map.get(x[1])+x[2]);
}

ArrayList<Integer> lender = new ArrayList<>();
for (int x : map.keySet()) {
int money = map.get(x);
if (money < 0)
else if (money > 0)
}

return ans;
}

private void helper(ArrayList<Integer> lender, ArrayList<Integer> receiver, int count) {
boolean flag = true;

for (int i = 0; i < lender.size(); i++) {
if (lender.get(i) != 0) {
flag = false;
for (int j = 0; j < receiver.size(); j++) {
int x = lender.get(i);
if (x > y) {
lender.set(i, x - y);
}
else if (x < y) {
lender.set(i, 0);
}
else {
lender.set(i, 0);
}
lender.set(i, x);
}
}
}
}
if (flag)
ans = Math.min(ans, count);
}
}
``````

• O(2^N) is the best possible, I guess, I also find some other code which is straightforward and easier to understand as well:

``````// Optimal Account Balancing
#define FOR(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)

class Solution {
public:
int minTransfers(vector<vector<int>>& t) {
unordered_map<int, int> m;
int r = 0, c = 0;
for (auto& x: t) {
m[x[0]] += x[2];
m[x[1]] -= x[2];
}
vector<int> a;
for (auto& x: m)
if (x.second)
a.push_back(x.second);
if (a.empty()) return 0;
vector<int> dp(1<<a.size(), INT_MAX/2), cir;
FOR(i, 1, 1<<a.size()) {
int t = 0, c = 0;
REP(j, a.size())
if (i>>j & 1)
t += a[j], c++;
if (! t) {
dp[i] = c-1;
for (int t: cir)
if ((i & t) == t)
dp[i] = min(dp[i], dp[t]+dp[i-t]);
cir.push_back(i);
}
}
return dp.back();
}
};
``````

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