# 465. Optimal Account Balancing

first, found the len is so samll, so it must a dfs backtracking problem

![](/files/TaSyy4ImM1OJDMOhr7oa)

![](/files/rYibCesWRQpAfIfABDqf)

T: O(n!), not sure, n is transactions array size

S: O(n)

```java
class Solution {
    public int minTransfers(int[][] transactions) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] t : transactions) {
            map.put(t[0], map.getOrDefault(t[0], 0) - t[2]);
            map.put(t[1], map.getOrDefault(t[1], 0) + t[2]);
        }
        
        return dfs(0, new ArrayList<>(map.values()));
    }
    private int dfs(int start, List<Integer> debt) {
        int n = debt.size();
        
        while (start < n && debt.get(start) == 0) {
            start++;
        }
        if (start == n) {
            return 0;
        }
        Integer res = Integer.MAX_VALUE;
        
        // 固定一個數(start), 對其他的數(for start+1 to n)做窮舉, 所以呼叫 dfs 要到下層是 start + 1 
        int prev = debt.get(start);
        for (int i = start+1; i < n; i++) {
            int cur = debt.get(i);
            if (prev * cur < 0) { // 一正一負時才 try dfs
                debt.set(i, cur + prev);
                res = Math.min(res, 1 + dfs(start+1, debt)); // count+1
                debt.set(i, cur); // 因為是 set, 所以不用 - prev (也可以 debt.get(i) - prev), 但反正有原始值
                
                if (prev + cur == 0) { // pruning, 已經平衡了, 就不用繼續 try
                    break;
                }
            }
        }
        return res;
    }
}

/*
minimum number of transactions required to settle the debt

[0,1,10],[2,0,5]

  5   10
2-> 0 -> 1

1 give 0 5
1 give 2 5

1 -10
0. 5
2. 5

*/
```

## global variable version

```java
class Solution {
    int res = Integer.MAX_VALUE;
    public int minTransfers(int[][] transactions) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] t : transactions) {
            map.put(t[0], map.getOrDefault(t[0], 0) - t[2]);
            map.put(t[1], map.getOrDefault(t[1], 0) + t[2]);
        }
        dfs(0, new ArrayList<>(map.values()), 0);
        return res;
    }
    private void dfs(int start, List<Integer> debt, int count) {
        int n = debt.size();
        
        while (start < n && debt.get(start) == 0) {
            start++;
        }
        if (start == n) {
            res = Math.min(res, count);
            return;
        }
        
        // 固定一個數(start), 對其他的數(for start+1 to n)做窮舉, 所以呼叫 dfs 要到下層是 start + 1 
        int prev = debt.get(start);
        for (int i = start+1; i < n; i++) {
            int cur = debt.get(i);
            if (prev * cur < 0) { // 一正一負時才 try dfs
                debt.set(i, cur + prev);
                dfs(start+1, debt, count+1); // count+1
                debt.set(i, cur); // 因為是 set, 所以不用 - prev (也可以 debt.get(i) - prev), 但反正有原始值
                
                if (prev + cur == 0) { // pruning, 已經平衡了, 就不用繼續 try
                    break;
                }
            }
        }
    }
}


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips/465.-optimal-account-balancing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.