• Time:O(n!)
• Space:O(n!)

## C++

``````class Solution {
public:
int minTransfers(vector<vector<int>>& transactions) {
vector<int> balance(21);
vector<int> debt;

for (const auto& t : transactions) {
const int from = t[0];
const int to = t[1];
const int amount = t[2];
balance[from] -= amount;
balance[to] += amount;
}

for (const int b : balance)
if (b)
debt.push_back(b);

return dfs(debt, 0);
}

private:
int dfs(vector<int>& debt, int s) {
while (s < debt.size() && !debt[s])
++s;
if (s == debt.size())
return 0;

int ans = INT_MAX;

for (int i = s + 1; i < debt.size(); ++i)
if (debt[i] * debt[s] < 0) {
debt[i] += debt[s];  // debt[s] is settled
ans = min(ans, 1 + dfs(debt, s + 1));
debt[i] -= debt[s];  // backtrack
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int minTransfers(int[][] transactions) {
int[] balance = new int[21];
List<Integer> debt = new ArrayList<>();

for (int[] t : transactions) {
final int from = t[0];
final int to = t[1];
final int amount = t[2];
balance[from] -= amount;
balance[to] += amount;
}

for (final int b : balance)
if (b != 0)

return dfs(debt, 0);
}

private int dfs(List<Integer> debt, int s) {
while (s < debt.size() && debt.get(s) == 0)
++s;
if (s == debt.size())
return 0;

int ans = Integer.MAX_VALUE;

for (int i = s + 1; i < debt.size(); ++i)
if (debt.get(i) * debt.get(s) < 0) {
debt.set(i, debt.get(i) + debt.get(s)); // debt.get(s) is settled
ans = Math.min(ans, 1 + dfs(debt, s + 1));
debt.set(i, debt.get(i) - debt.get(s)); // backtrack
}

return ans;
}
}
``````

## Python

``````class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
balance = [0] * 21

for u, v, amount in transactions:
balance[u] -= amount
balance[v] += amount

debt = [b for b in balance if b]

def dfs(s: int) -> int:
while s < len(debt) and not debt[s]:
s += 1
if s == len(debt):
return 0

ans = math.inf

for i in range(s + 1, len(debt)):
if debt[i] * debt[s] < 0:
debt[i] += debt[s]  # debt[s] is settled
ans = min(ans, 1 + dfs(s + 1))
debt[i] -= debt[s]  # backtrack

return ans

return dfs(0)
``````