Introduction

Expense-settlement problems appear in travel apps, household budgeting tools, and team reimbursement systems. The core task is simple to state: after everyone has paid different amounts, compute who should pay whom so that each person's net balance becomes zero.

Model the Problem as Net Balances

Start by computing each participant's net position.

• positive balance means the person should receive money
• negative balance means the person owes money
• zero means they are already settled

For equal splitting, the formula is:

net balance = amount paid - fair share

Once you have net balances, the original list of purchases no longer matters for settlement. The remaining problem is just matching debtors to creditors.

Consider this example:

• Alice paid 120
• Ben paid 20
• Cara paid 60

The total is 200, so each person should pay 200 / 3 = 66.67.

• Alice: +53.33
• Ben: -46.67
• Cara: -6.67

A valid settlement is Ben pays Alice 46.67, and Cara pays Alice 6.67.

A Practical Greedy Algorithm

A standard approach is to separate creditors and debtors, then repeatedly settle the largest remaining amounts.

1from collections import deque
2
3
4def settle(balances):
5    creditors = deque(sorted(
6        [(name, amount) for name, amount in balances.items() if amount > 1e-9],
7        key=lambda x: x[1]
8    ))
9    debtors = deque(sorted(
10        [(name, -amount) for name, amount in balances.items() if amount < -1e-9],
11        key=lambda x: x[1]
12    ))
13
14    transactions = []
15
16    while creditors and debtors:
17        creditor_name, credit = creditors.pop()
18        debtor_name, debt = debtors.pop()
19
20        payment = min(credit, debt)
21        transactions.append((debtor_name, creditor_name, round(payment, 2)))
22
23        credit -= payment
24        debt -= payment
25
26        if credit > 1e-9:
27            creditors.append((creditor_name, credit))
28        if debt > 1e-9:
29            debtors.append((debtor_name, debt))
30
31    return transactions
32
33
34balances = {
35    "Alice": 53.33,
36    "Ben": -46.67,
37    "Cara": -6.66,
38}
39
40print(settle(balances))

This runs quickly and produces clean payment instructions.

What This Algorithm Optimizes

The greedy method guarantees that balances are settled correctly. It also tends to keep the number of transactions low because each step completely clears either one debtor or one creditor.

However, it is important to be precise: greedy settlement is practical, but it does not always prove the absolute minimum number of transactions across all possible solutions. For most real applications, that tradeoff is acceptable because the algorithm is simple, fast, and easy to explain.

If you truly need the fewest transactions possible, you usually move into backtracking or search-based methods on the reduced balance vector. Those exact methods are better for small groups than for large production workloads.

Unequal Splits and Weighted Shares

Real expense apps often need more than equal division. A trip might split hotel costs equally but divide dinner based on attendance. The correct pattern is:

1. compute each person's final fair share from business rules
2. subtract that from what they actually paid
3. settle the resulting net balances

The settlement stage stays the same even if the share calculation is complex.

def compute_balances(paid, owed):
    return {name: round(paid[name] - owed[name], 2) for name in paid}

This separation keeps the code maintainable.

Precision and Rounding

Currency arithmetic can create tiny residual errors. A balance like -0.0000001 should not trigger a new transaction.

Use a small tolerance when deciding whether someone still owes money, and prefer fixed-precision decimal arithmetic if the system handles real money.

In Python, decimal.Decimal is usually safer than binary floating point for production billing logic.

Scaling to Larger Groups

The net-balance representation is compact. Even if thousands of raw expenses exist, settlement only depends on the final participant balances.

That means the expensive part is often not the settlement algorithm itself, but the earlier step that determines fair shares from all expense records, exceptions, participants, and business rules.

Once balances are computed, a greedy pass is typically fast enough for interactive apps.

Common Pitfalls

A common mistake is trying to preserve the original payment graph. That usually creates far more transactions than necessary. Settlement should start from net balances, not from every raw expense edge.

Another pitfall is claiming a greedy algorithm always gives the globally minimum number of transfers. It is a strong heuristic and often good enough, but not a proof of optimality in every case.

Developers also get tripped up by rounding. If the sum of balances is not exactly zero after rounding, handle the residual carefully or the UI will show impossible leftovers.

Summary

• Reduce the problem to net balances before generating transfers.
• A greedy debtor-creditor matching algorithm is simple and effective.
• The same settlement logic works for equal or weighted splits.
• Use decimal-safe arithmetic and tolerances for money.
• Greedy settlement is practical, but exact minimum-transfer optimization is a different problem.