Skip to content

465. Optimal Account Balancing 👍

  • Time: $O(n!)$
  • Space: $O(n!)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
 public:
  int minTransfers(vector<vector<int>>& transactions) {
    vector<int> balance(21);
    vector<int> debt;

    for (const vector<int>& 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 > 0)
        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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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)
        debt.add(b);

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)