# Minimum transactions to settle debts: the algorithm

Canonical URL: https://www.evenoutapp.com/guides/minimum-transactions-to-settle-debts
Updated: 2026-10-06

Turn every expense into one net balance per person, then match debtors to creditors. Greedy matching settles N people in at most N minus 1 payments but can miss the minimum. The true minimum is N minus the largest number of zero-sum groups you can carve out, and finding the best split into such groups is hard in general.

Key points:
- Every settlement starts from net balances: what a person paid minus their fair share. Payments never change the fact that nets add up to zero.
- Matching the largest debtor with the largest creditor settles N people in at most N minus 1 payments.
- Owed $10 and $7 against owing $4, $6 and $7 takes 4 payments greedily, but only 3 because two sets of people cancel exactly.
- The fewest payments possible is N minus the largest number of zero-sum groups, and finding that number is NP-hard in general.

## What is the debt simplification problem?

A group has run up a tangle of IOUs, and you want to settle all of them with as few payments as possible. The only number you need for each person is their net balance: what they paid minus their fair share of everything. Payments move money around, but they never break one rule: every net balance in the group adds up to zero, because every dollar someone is owed is a dollar someone else owes.

That makes the problem small. Forget who bought what for whom. Keep one number per person and find the fewest payments that bring every number to zero.

## How do you get each person's net balance?

Say five friends split $100 of weekend costs equally, so the fair share is $20 each. A paid $30 of the costs, B paid $27, C paid $16, D paid $14 and E paid $13.

| Person | Paid | Fair share | Net balance |
|---|---|---|---|
| A | $30 | $20 | Owed $10 |
| B | $27 | $20 | Owed $7 |
| C | $16 | $20 | Owes $4 |
| D | $14 | $20 | Owes $6 |
| E | $13 | $20 | Owes $7 |

Check the two sides. A and B are owed $10 + $7 = $17, and C, D and E owe $4 + $6 + $7 = $17. If they do not match, an expense is missing or a rounded share is off, so fix that before looking for payments. Anyone at exactly zero needs no payment and drops out. From here, N means the number of people still in.

## How does the greedy method settle the group?

The greedy method repeats one step: take the person who owes the most and the person who is owed the most, and have the first pay the second as much as they can.

1. E (owes $7) pays A (owed $10) $7. E is done and A is still owed $3.
2. D (owes $6) pays B (owed $7) $6. D is done and B is still owed $1.
3. C (owes $4) pays A $3. A is done and C still owes $1.
4. C pays B $1. Everyone is square.

That is 4 payments moving $17 in total. It can never take more than N minus 1 payments, and for five people that is 4. The reason is that every payment finishes at least one person, since the payer clears their whole debt or the receiver gets their whole credit. The last payment finishes two people at once, because the balances add to zero. So N people are done in at most N minus 1 payments.

## Is 4 payments the fewest for this group?

No. The same group settles in 3 payments. Look for sets of people whose balances cancel exactly:

- **A, C and D:** A is owed $10, and C and D owe $4 + $6 = $10.
- **B and E:** B is owed $7 and E owes $7.

Each set can settle among itself. C pays A $4 and D pays A $6, which is 2 payments. E pays B $7, which is 1 payment. That is 3 payments, and the same $17 moves. The greedy method missed it because step 1 sent E's $7 to A, when E's debt matches B's credit exactly.

## What is the true minimum number of payments?

The minimum is N minus the largest number of zero-sum groups you can split everyone into. A zero-sum group is a set of people whose balances add to exactly zero. Here N is 5 and the best split has 2 groups, so the minimum is 5 minus 2, which is 3.

Here is why. Draw a line between two people whenever one pays the other. Linked people form clusters, and money cannot leave a cluster, so each cluster's balances must add to zero. A cluster of k people needs at least k minus 1 lines to hold together, and k minus 1 payments are enough to settle it, by the same argument as the greedy bound. With c clusters, the total is at least N minus c, and you reach it when c is as large as possible. If nobody can be split off, c is 1 and the answer is N minus 1, which is what greedy gives.

One shortcut is always safe. Two people whose balances are exact opposites, such as owed $7 and owing $7, can be paired off, and pairing them never costs you an extra payment.

## Why is finding the best split hard?

To find the most zero-sum groups, you have to find which sets of people add to zero. Five people have 31 non-empty sets to test. Each extra person doubles the count, so 20 people have more than a million sets and 30 people have more than a billion.

For a weekend with five or six people, you can do it on paper in a minute:

1. Work out each net balance and check that they add to zero.
2. Pair off exact opposites.
3. Look for three people where two balances add up to the third, as owing $4 and $6 do against being owed $10.
4. Settle whatever is left greedily.

For large groups the difficulty does not go away. Patcas and Bartha note that settling with as few transfers as possible is known to be NP-hard in the strong sense, which means no known method stays fast on every large group. Tom Verhoeff's 2004 paper in Informatics in Education poses several debt-settling problems for bright high-school students and describes one variant as an elegant NP-hard problem.

## What does this mean for the apps you use?

An app that simplifies debts is working on this same problem. As of October 2026, Splitwise's help center says Simplify Debts "restructures who owes whom within a group to minimize the total number of payments needed for everyone to settle up" and that it "never changes anyone's total balance", which is the net-balance rule above. It also says it works within each currency separately, so the steps here run once per currency. How a given app searches for its answer is its own design, so you can check any app by counting. If it shows more payments than N minus the zero-sum groups you can find by hand, a shorter way exists.

In EvenOut, Simplify debts is a group setting under "Settling up", tagged "Recommended" and on by default, described as "Fewer payments, same totals." Any member who is not a viewer can switch it. [How simplify debts works](https://www.evenoutapp.com/guides/how-simplify-debts-works) walks through six IOUs in a group of four, and the [debt simplification calculator](https://www.evenoutapp.com/tools/debt-simplification-calculator) lets you try your own balances.

## What should you do next?

Work out your group's net balances first, since every method starts there. [How to figure out who owes who](https://www.evenoutapp.com/guides/who-owes-who) covers that step with shared expenses, and [apps that simplify debts](https://www.evenoutapp.com/alternatives/apps-that-simplify-debts) lists which apps offer the setting and whether you can turn it off.

## Frequently asked questions

### How many payments can a group of 10 need at most?

At most 9 if all ten people have a balance. Anyone at exactly zero needs no payment and drops out of the count, so a group of 10 with two people at zero needs at most 7. It is often fewer, because some balances cancel in groups.

### What happens to the answer when someone has already paid part of what they owe?

The nets change, so work them out again. In the five-person example, if D has already paid A $6, then A is owed $4, D is at zero, and the group settles in 2 payments: C pays A $4 and E pays B $7.

### Can rounding stop a group from netting to zero?

Yes. If each share is rounded on its own, the shares can be a cent off the bill. Hand the leftover cents to specific people so the shares add up to the bill exactly, and the nets will sum to zero. EvenOut does this: remainder cents are shared out, not lost.

### Do two currencies cancel each other out?

No. A balance in dollars cannot cancel a balance in euros, so run the steps once per currency. As of October 2026, Splitwise says its Simplify Debts works within each currency separately, and EvenOut also keeps simplify per currency.

## Sources

- [Tom Verhoeff: Settling Multiple Debts Efficiently: An Invitation to Computing Science, Informatics in Education 3(1), 2004](https://infedu.vu.lt/journal/INFEDU/article/612/info)
- [Csaba Patcas and Attila Bartha: Evolutionary solving of the debts clearing problem (arXiv, 2014)](https://arxiv.org/abs/1402.6556)
- Splitwise: What is Simplify Debts?