Optimal Account Balancing

Optimal Account Balancing is a classic backtracking problem hiding inside a money puzzle. A group of friends has lent and borrowed from each other; we want to settle all debts with the fewest possible transactions. The key realization: individual transactions do not matter — only each person's net balance does.

The slow way first

You might try to be clever about which debts to cancel, but the only honest approach is to try every way of pairing debtors with creditors and keep the cheapest. That is exponential, and there is no simple greedy rule that is always correct (greedily matching equal amounts can miss better global pairings). So we search — but we shrink the problem first.

The question to ask: what actually has to happen? If person 0 owes 10 in total and is owed 4, all that matters is their net of −6. Names and individual loans wash out.

The idea: net balances, then DFS

First, collapse every transaction into a net balance per person: paying money makes you more negative, receiving makes you more positive. Throw away anyone whose net is 0 — they are already settled. What remains is a list bal of nonzero balances that always sums to zero.

Now DFS over that list: take the first unsettled balance bal[i] and pay it off against every later balance of the opposite sign. Each such pairing costs one transaction; recurse to settle the rest, and keep the minimum over all choices.

Settling bal[i] against bal[j] means bal[j] += bal[i] (the debt moves onto j), then we undo it after the recursive call so the next branch starts clean — that undo is the backtracking step.

Walk through it

Step through the animation. We start from net balances [-10, +5, +5, -5, +5]. The first balance, −10, is paid against the +5 at index 1, turning it into −5. Then that −5 is paid against the next +5, clearing two people. Finally the remaining −5 and +5 cancel. Three transactions settle everyone, and the search confirms nothing does better.

Pseudocode

net = {}                                  # net balance per person
for (a, b, amt) in transactions:
    net[a] -= amt                          # a paid, so a is more negative
    net[b] += amt                          # b received, so b is more positive
bal = [v for v in net if v != 0]           # drop anyone already settled
 
define dfs(i):
    skip over any bal[i] that is already 0
    if we reached the end: return 0        # everyone settled
    best = infinity
    for each j after i with opposite sign:
        bal[j] += bal[i]                    # one transaction settles i
        best = min(best, 1 + dfs(i + 1))
        bal[j] -= bal[i]                    # backtrack
    return best
 
return dfs(0)

The Python solution

def min_transfers(transactions):
    net = {}
    for a, b, amt in transactions:
        net[a] = net.get(a, 0) - amt
        net[b] = net.get(b, 0) + amt
    bal = [v for v in net.values() if v != 0]
 
    def dfs(i):
        while i < len(bal) and bal[i] == 0:
            i += 1
        if i == len(bal):
            return 0
        best = float('inf')
        for j in range(i + 1, len(bal)):
            if bal[j] * bal[i] < 0:
                bal[j] += bal[i]
                best = min(best, 1 + dfs(i + 1))
                bal[j] -= bal[i]
        return best
 
    return dfs(0)

• net accumulates each person's signed total; the payer goes down, the receiver goes up.
• bal keeps only the nonzero balances — settled people add nothing to the count.
• In dfs, the while loop skips balances that already hit zero, and reaching the end means everyone is settled, so we return 0.
• The for loop tries pairing bal[i] with every later bal[j] of opposite sign (bal[j] * bal[i] < 0).
• Lines 16 and 18 are the heart of backtracking: apply the transfer, recurse, then undo it so the next branch is unaffected.

Complexity

Here n is the number of people with a nonzero balance — usually far smaller than the transaction count, which is why collapsing to net balances first matters so much. The recursion depth is at most n.

When this pattern shows up

Practice