How a 70-line algorithm cuts a tangled web of seven debts down to four transfers - explained step by step with no computer science background needed.
Five housemates, an old fridge to replace, the Wi-Fi that's been on one person's card all year, the takeaway run last Friday. By the end of the month there are seventeen unsettled debts between five people. The naive answer is seventeen transfers. The actual answer is four.
Splitwise built a brand on the algorithm that gets you from seventeen to four. Tricount has it. Settle Up has it. We have it. Below is what it does, why it works, and how to think about it without a computer-science background.
Net everyone's position to a single balance. Sort balances into "owed money" and "owes money" piles. Match the most-owed person against the most-owing person, partial-pay until one of them hits zero, recurse. The result is at most (N-1) transfers for N people.
Let's start small. Three people: A, B, C.
That's six debts to settle. Naive: six transfers. We can do better.
For each person, sum (what they paid) minus (what they owe).
Sanity check: the nets must sum to zero. +45 + 5 - 15 = 35. That's not zero - I made an arithmetic mistake somewhere.
Let me recompute. A's £60 was for dinner; B and C each owe £20, so A is owed £40 from that. A's shares of the cinema (£10) and taxi (£5) come out of that, leaving A net +£25.
Better. Let me redo all three:
Sum: 25 - 5 - 20 = 0. Now it balances. (The arithmetic mistake above is exactly the kind of thing that makes humans hate doing this manually, which is why we automate it.)
Two piles:
The largest creditor is A (£25). The largest debtor is C (£20). C transfers £20 to A.
Update the piles:
Now the largest creditor is A (£5). The largest debtor is B (£5). B transfers £5 to A.
Update:
Everyone is at zero. We're done.
Total transfers: 2. Compared to the naive 6.
Two reasons.
Netting reduces the problem.Once we've netted, we don't care who owed whom for which expense. We only care about the per-person balance. That collapses an N×N matrix of debts into an N-element vector of net balances.
Greedy matching minimises transfer count. Each transfer either settles one party (zeros their balance) or both. Settling one party removes them from the problem. With N non-zero-balance people, at most N-1 transfers are needed because the last one must, by conservation, settle two parties at once.
That N-1 bound is the upper bound. Sometimes you do better - if two people happen to owe equal amounts to a third, two transfers settle three people (one transfer settles two). On average, the algorithm gets you about 60% fewer transfers than the naive approach.
Almost. The greedy algorithm is provably within a small factor of optimal, but not always exactly optimal. The truly optimal version is a known NP-hard problem (it reduces to subset-sum), which means there's no efficient algorithm guaranteed to find the absolute minimum number of transfers for arbitrary inputs.
For real groups (3-15 people), the difference between greedy and optimal is usually 0 transfers, occasionally 1. We trade theoretical perfection for an algorithm that runs in microseconds and produces obvious, explainable results.
Let's do five people with bigger numbers.
Net balances after a month of housemate expenses:
Sum: 80 + 35 - 15 - 40 - 60 = 0. Good.
Run the algorithm:
Total: 4 transfers. With 5 people, that's the upper bound (N-1).
The naive approach would have produced however many pairwise debts existed - typically 10-20 for a busy month. The greedy algorithm is doing real work.
Real money has minimum units (pennies, cents, yen). When you net balances, you can end up with sub-penny remainders. We handle this by working in minor units throughout (pence as integers, not £ as floats), so there are no float-precision bugs. Any rounding at the very end gets distributed in a stable order so the same people always pick up the rounding penny.
We have more on this in rounding cents in a settlement: who gets the extra penny?.
If the group has expenses in EUR and GBP, every expense gets converted to the group's default currency (using mid-market rates locked at expense-time) before the netting happens. The settle-up plan is always denominated in one currency. We covered the FX side in mid-market rates explained, without the jargon.
What if someone wants to pay off only part of their balance now? The algorithm handles it. After the partial payment, balances get updated and the algorithm re-runs on the residual. We have a deeper dive in partial settlements: paying down a balance incrementally.
When you tap Settle up in EvenRound, this is the actual flow:
The whole pipeline runs in 30-150ms, depending on group size. It's the kind of feature that disappears once you have it - you stop noticing the maths because you don't have to do it.
Sixty lines of TypeScript do the work. Sort the balances. Two pointers - one at the most-positive, one at the most-negative. Match them, partial-settle, advance the pointer of whichever hit zero. Repeat until both pointers cross.
The whole implementation lives in our settlement library and is property-tested with hundreds of randomly generated groups per CI run, ensuring it never produces a settlement that fails to balance.
For groups of 15+ people, the greedy algorithm is occasionally sub-optimal in a noticeable way. There's a more sophisticated version using minimum-spanning-tree on a flow graph that gives provably optimal results for medium-sized inputs. We haven't implemented it yet because the marginal user benefit is small and the implementation complexity is high. If we did, the promise would be "even fewer transfers in big groups". Filed under: nice to have.
Create a group, add a few expenses, tap Settle up. The transfers you see are the output of this algorithm. Net balance, greedy match, done.
Free forever. No signup. Works in your browser in 30 seconds.