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

    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)
        debts.push_back(b);

    return dfs(debts, 0);
  }

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

    int ans = INT_MAX;

    for (int i = s + 1; i < debts.size(); ++i)
      if (debts[i] * debts[s] < 0) {
        debts[i] += debts[s];  // `debts[s]` is settled.
        ans = min(ans, 1 + dfs(debts, s + 1));
        debts[i] -= debts[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> debts = 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)
        debts.add(b);

    return dfs(debts, 0);
  }

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

    int ans = Integer.MAX_VALUE;

    for (int i = s + 1; i < debts.size(); ++i)
      if (debts.get(i) * debts.get(s) < 0) {
        debts.set(i, debts.get(i) + debts.get(s)); // `debts.get(s)` is settled.
        ans = Math.min(ans, 1 + dfs(debts, s + 1));
        debts.set(i, debts.get(i) - debts.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

    debts = [b for b in balance if b]

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

      ans = math.inf

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

      return ans

    return dfs(0)