Optimal Account Balancing

Free with account Updated Nov 19, 2026 · 7 min read
On this page

    Problem statement

    A group of friends recorded who lent money to whom. Each record is [lender, borrower, amount]. Return the minimum number of payments needed so that everyone ends up even. Any person may pay any other person any amount.

    This is the "split the bill" problem behind expense-sharing apps, and a favourite at payments and fintech companies. It looks like a graph problem, but the key step is throwing the graph away: only each person's net balance matters. Original problem: LeetCode 465.

    Example

    Three loans leave Alice +6, Bob +4, Carol −4 and Dan −6; two payments settle everything.
    Three loans leave Alice +6, Bob +4, Carol −4 and Dan −6; two payments settle everything.
    Input:  [[Alice, Bob, 6], [Bob, Carol, 10], [Carol, Dan, 6]]   # as ids: [[0,1,6],[1,2,10],[2,3,6]]
    Net:    Alice +6, Bob +4, Carol -4, Dan -6
    Output: 2      # Dan pays Alice 6, Carol pays Bob 4
    Input:  [[0,1,5], [1,0,5]]
    Output: 0      # the two loans cancel out

    Constraints (assumed)

    • 1 ≤ number of records ≤ 8; person ids are small integers; amounts are positive.
    • After netting, at most about 12 people have a non-zero balance. That small limit is a hint that exponential search is expected.

    What this question tests

    • Reducing the input to net balances and ignoring who originally lent to whom.
    • Seeing that greedy settling is not optimal, and that the real goal is to find many disjoint groups that sum to zero.
    • Writing a backtracking search with pruning that is fast enough, or the equivalent bitmask DP.

    Questions to ask first

    1. Can anyone pay anyone, even people who never traded directly? (Here: yes.)
    2. Do we count payments or total money moved? (Here: the number of payments. Total money moved is always the same: the sum of the positive balances.)
    3. How many people can there be? The answer decides between exponential search and "good enough" greedy.
    4. Are amounts integers? (Here: yes. With money, use cents to avoid float errors.)