How to settle group debts with the fewest payments

At the end of a shared trip the ledger looks like a knot. You owe Ana, Ana owes Ben, Ben owes you, and somebody suggests everyone just pays everyone. You don't have to. There is a rule that takes any group to the smallest realistic set of payments, an upper limit that no app can beat, and one genuinely hard problem hiding underneath — which turns out to matter far less than the people who write about it imply.

First, forget who bought what

The biggest reduction happens before any clever algorithm, and it costs nothing. Stop tracking debts expense by expense and reduce each person to one number: everything they paid, minus everything they owed. Positive means the group owes them. Negative means they owe the group. Those numbers always add up to zero — if they don't, an expense has been entered wrong, and that check alone is worth doing.

That step does most of the work, because it throws away the structure that made the knot in the first place. Once Ana is simply "+€130", it stops mattering which four dinners got her there.

Twenty payments becomes three

Five friends share a house for a week and spend €600 between them — €120 each. Who paid varies wildly:

• Ana pays €250 for the villa deposit
• Ben pays €180 for groceries
• Cara pays €120 for fuel
• Dan pays €30 for coffee
• Eve pays €20 for parking

Settled the obvious way — after each expense, the four people who didn't pay hand their share to the one who did — that is 20 separate payments for a week away.

Net it instead, and five numbers are left:

• Ana +€130
• Ben +€60
• Cara €0
• Dan −€90
• Eve −€100

Now match the largest debt to the largest credit, over and over. Eve owes the most at €100; Ana is owed the most at €130:

1. Eve pays Ana €100. Eve is clear. Ana is still owed €30.
2. Dan pays Ana €30. Ana is clear. Dan still owes €60.
3. Dan pays Ben €60. Everyone is clear.

Three payments instead of twenty — and, as the next section shows, the arithmetic guaranteed before we started that it could never have been more than four.

You never need more than one payment per person, minus one

This is the most useful thing in this article, and it takes one line to see why it's true.

Every payment in that matching zeroes out at least one person: either the debtor clears their balance, or the creditor is made whole, or both at once. So each payment retires at least one participant, and the final payment always retires two. With k people holding non-zero balances, you are finished in at most k−1 payments. Anyone already at zero — Cara — drops out and doesn't count toward k.

Keep that number to hand when a group starts designing a settlement scheme. If six people are discussing a plan with eight payments in it, the plan is wrong, not sophisticated.

When the fewest is fewer still

Matching biggest-to-biggest is a heuristic, and heuristics have edges. Here is the smallest realistic case where it costs a payment. Five people end a weekend with these balances: +€40, +€30, +€20, −€50 and −€40.

Matching largest first: the −€50 pays €40 to the +€40, then €10 to the +€30. The −€40 then pays €20 to the +€30 and €20 to the +€20. Four payments.

But look at the numbers again. The +€40 and the −€40 cancel each other exactly. And the three that remain — +€30, +€20 and −€50 — cancel among themselves. That's two self-contained little groups and three payments in total: one person settles €40, and the −€50 pays €30 and €20 to the other two. The heuristic never sees it, because it committed the −€50 to the +€40 before noticing that the −€40 was a perfect match.

Spotting those hidden zero-sum subsets is the entire difficulty, and it is a known hard problem. Tom Verhoeff's 2004 paper for Informatics in Education calls this variant "an elegant NP-hard problem", and Anton Cao gives an independent proof by reduction from Subset Sum. "Hard" is meant technically: as the group grows, guaranteeing the true minimum takes more work than any practical algorithm can absorb. So no app solves it exactly — and to be clear, Dolio doesn't either. The matching described above is precisely what Dolio runs.

So how often does that actually matter?

This is where every other explanation stops. The caveat gets stated, sometimes rigorously proved, and then never quantified — and the demonstrations are adversarial by design. Anton Cao's example is a constructed group of 42 people. Nobody has a group of 42 people.

So we measured it at the sizes people actually have. We generated 20,000 random groups of three to eight people, ran each through the same code Dolio runs in production, and compared every result against an exhaustive search for the true minimum:

• Three to six people: not a single miss in 13,172 groups.
• Seven people: 10 misses in 3,400 groups (0.3%).
• Eight people: 11 misses in 3,428 groups (0.3%).
• Overall: 21 groups out of 20,000 — the shortcut was optimal 99.9% of the time.
• Every miss cost exactly one extra payment. Never two.

We also ran the case that should favour the exact solver: 5,000 groups built entirely out of pairs that offset each other perfectly, where hidden cancellation is the norm rather than the exception. The heuristic found the optimum every single time, because sorting by size hands equal-and-opposite pairs straight to each other.

Couples and shared wallets change the answer

There is one case where the payment count drops further, and it isn't algorithmic at all — it's about who counts as a person.

If two people share money in real life, a debt between them isn't really a debt. Take three people: Ana pays €90 for something split three ways, and Ben pays €30 for something split three ways. The nets come out as Ana +€50, Ben −€10, Cara −€40. Treated as three individuals that needs two payments — Cara pays Ana €40, and Ben pays Ana €10.

Treat Ana and Ben as a couple and their balances collapse into a single +€40 before any matching happens. Cara pays €40 and the group is settled, in one payment. The €10 between Ana and Ben hasn't evaporated — it has stopped being the group's business, which is an accurate description of a shared wallet. Dolio calls these subgroups, and nets them before it simplifies anything.

Doing it by hand

No app required — this works on the back of a receipt:

1. Write down what each person paid in total.
2. Write down what each person owed in total — their share of every expense they were part of.
3. Subtract, leaving one number per person. Check the numbers sum to zero; if they don't, an expense is wrong.
4. Cross off anyone sitting at zero. They are finished.
5. Repeatedly take the largest amount owed and the largest amount due, and move the smaller of the two between those people. Cross off whoever hits zero.
6. Stop when everyone is at zero. You will have used fewer payments than the number of people left after step 4.

One refinement beats the algorithm: before you start step 5, scan for two numbers that are equal and opposite and pair them off directly. That is exactly the case the shortcut can miss, and it is easy to spot by eye in a small group.

Where Dolio fits

Dolio nets balances and runs this matching automatically every time an expense changes, including the subgroup step — that's the transfer minimization feature. It is on the free plan, because it isn't a premium trick; it's arithmetic. If you'd rather keep doing it by hand, the recipe above is genuinely all of it — and our spreadsheet-versus-app comparison is honest about when a sheet is the better tool. For a worked example with awkward real-world weighting, see splitting an Airbnb between people staying different nights.