Debt Simplification: How to Settle Group Expenses in the Fewest Transfers

To settle a group’s shared expenses in the fewest transfers, ignore who paid for what and compute each person’s net balance: total paid minus their share of everything. Then repeatedly match the person who owes the most with the person who is owed the most, transfer the smaller of the two amounts, and repeat. This greedy approach settles any group of n people in at most n − 1 transfers, runs in O(n log n) with a heap, and never changes how much anyone ends up paying.

It is not always the absolute minimum. Finding the true minimum is NP-hard, and in our simulations of 17,000 groups the greedy method was optimal almost every time with realistic amounts, but fell short in up to 65% of groups when everyone split round numbers. Below we walk through the problem, a worked example, TypeScript code, the simulation results, and how to get the true optimum for small groups.

The problem: a web of IOUs

Picture ten friends on a week-long trip. Different people pay for the flat, groceries, taxis and dinners, and not everyone joins every activity. If each person repaid exactly the people they owe, expense by expense, you would get a dense web of debts. Even after netting each pair of people against each other, a group of n people can have up to n(n − 1)/2 separate debts: 45 for ten people.

Every one of those transfers costs time, sometimes fees, and a small moment of social friction (we cover why in the psychology of splitting the bill). Debt simplification collapses the web into as few transfers as possible while guaranteeing everyone pays exactly what they owe overall.

Modeling shared expenses as a graph

Model the group as a directed, weighted graph. Each person is a node. An edge from A to B with weight €20 means A owes B €20. Settling up means replacing this graph with a new set of edges, the transfers, such that every node’s net flow is unchanged.

The key observation is that only net flow matters. If Alice owes Bob €10 and Bob owes Alice €4, the only thing that has to happen is that Alice ends up €6 poorer and Bob €6 richer. Cycles cancel out the same way: if A owes B, B owes C and C owes A the same amount, nobody needs to pay anyone.

Step 1: Calculate net balances

For each person, add everything they paid and subtract their share of every expense they took part in. Positive means the group owes them; negative means they owe the group. Balances always sum to zero. Work in integer cents, not floating point, and distribute rounding remainders deterministically so the sum stays exactly zero.

type Expense = { paidBy: string; amountCents: number; splitAmong: string[] };

function netBalances(expenses: Expense[]): Map<string, number> {
  const balance = new Map<string, number>();
  const add = (id: string, cents: number) => balance.set(id, (balance.get(id) ?? 0) + cents);

  for (const e of expenses) {
    const n = e.splitAmong.length;
    const base = Math.floor(e.amountCents / n);
    let remainder = e.amountCents - base * n; // distribute leftover cents deterministically
    for (const person of e.splitAmong) {
      const share = base + (remainder-- > 0 ? 1 : 0);
      add(person, -share);
      add(e.paidBy, share);
    }
  }
  return balance; // positive = is owed money, negative = owes money; always sums to 0
}

Step 2: Match debtors and creditors greedily

• Split people into creditors (positive balance) and debtors (negative balance).
• Take the largest debtor and the largest creditor.
• Transfer the smaller of the two amounts from the debtor to the creditor. At least one of them is now at zero.
• Repeat until every balance is zero.

Each transfer brings at least one person to zero, and the last transfer always settles two people at once, so the algorithm needs at most n − 1 transfers for n people with a non-zero balance.

type Transfer = { from: string; to: string; amountCents: number };

function simplifyDebts(balance: Map<string, number>): Transfer[] {
  const creditors = [...balance].filter(([, b]) => b > 0).map(([id, b]) => ({ id, amt: b }));
  const debtors = [...balance].filter(([, b]) => b < 0).map(([id, b]) => ({ id, amt: -b }));
  const transfers: Transfer[] = [];

  // Largest first. A binary heap makes this O(n log n); sorting each round is fine for groups.
  while (creditors.length && debtors.length) {
    creditors.sort((a, b) => b.amt - a.amt);
    debtors.sort((a, b) => b.amt - a.amt);
    const c = creditors[0];
    const d = debtors[0];
    const amountCents = Math.min(c.amt, d.amt);

    transfers.push({ from: d.id, to: c.id, amountCents });
    c.amt -= amountCents;
    d.amt -= amountCents;
    if (c.amt === 0) creditors.shift();
    if (d.amt === 0) debtors.shift();
  }
  return transfers; // at most n - 1 transfers for n people with a non-zero balance
}

A worked example

Four friends share a weekend away. After all expenses are logged, their net balances are:

• Largest debtor Bob (−€110) pays largest creditor Alice (+€170) €110. Alice is now +€60, Bob is settled.
• Dev (−€110) pays Alice (+€60) €60. Alice is settled, Dev is now −€50.
• Dev (−€50) pays Chloé (+€50) €50. Everyone is settled.

Three transfers instead of the six pairwise debts four people could have. Three is also the minimum here: no smaller group of these four balances adds up to zero, so the group cannot be split into independent parts.

Why the true minimum is NP-hard

Here is the insight that makes the problem hard. Suppose you can split the group into k disjoint subgroups whose balances each sum to zero. Each subgroup can settle on its own in (size − 1) transfers, so the whole group settles in n − k transfers. The minimum number of transfers is therefore n minus the largest number of zero-sum subgroups you can find.

Even deciding whether a single proper zero-sum subgroup exists, which is what it takes to beat n − 1 transfers, is a version of the subset-sum problem, which is NP-complete. So there is no known algorithm that finds the true minimum efficiently for large groups. The greedy algorithm is fast precisely because it does not try.

A case where greedy is not optimal

Five people end a trip with these balances: Ana +€20, Ben +€20, Chloé +€30, Dev −€30, Eli −€40.

The optimal solution spots two independent zero-sum subgroups, {Chloé, Dev} and {Ana, Ben, Eli}, and settles them separately. Greedy matches the two largest balances first, Eli and Chloé, which breaks both subgroups apart.

Getting the exact minimum for small groups

NP-hard does not mean impractical at the size of a typical group. A dynamic program over subsets computes the maximum number of zero-sum subgroups exactly. It runs in O(2ⁿ · n) time, which is instant for a dinner or a trip and still fast for around 20 people with a non-zero balance.

// Exact minimum via bitmask DP over zero-sum subgroups. O(2^n * n): fine up to ~20 people.
function minTransfers(balancesCents: number[]): number {
  const v = balancesCents.filter((b) => b !== 0);
  const n = v.length;
  const full = 1 << n;
  const sum = new Array<number>(full).fill(0);
  const groups = new Array<number>(full).fill(0); // max zero-sum subgroups within mask

  for (let mask = 1; mask < full; mask++) {
    const low = 31 - Math.clz32(mask & -mask);
    sum[mask] = sum[mask ^ (1 << low)] + v[low];
    let best = 0;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) best = Math.max(best, groups[mask ^ (1 << i)]);
    }
    groups[mask] = best + (sum[mask] === 0 ? 1 : 0);
  }
  return n - groups[full - 1];
}

Once you know which zero-sum subgroups the optimum uses, run the greedy matching inside each subgroup to produce the actual transfers.

How often is greedy good enough? Results from 17,000 simulated groups

To see how much the theory matters in practice, we simulated 17,000 groups. Each group of n people logged 5n expenses. Every expense had a random payer and was shared among a random subset of two or more members. We compared three things: the number of debts left after netting each pair of people, the greedy result, and the exact minimum from the dynamic program.

We ran two scenarios. In the first, expense amounts were arbitrary values between €5 and €200 in cents, like real receipts. In the second, each participant’s share was a round number between €5 and €30, like splitting a flat entry fee or a fixed-price menu.

• Simplification matters far more than optimality. For ten people it turns roughly 45 pairwise debts into 8 or 9 transfers.
• With arbitrary amounts, zero-sum subgroups almost never occur by chance, so nearly every group needs exactly n − 1 transfers and greedy is effectively optimal.
• With round numbers, zero-sum subgroups are common. Greedy missed the minimum in about half of 10-person groups and two-thirds of 12-person groups, though never by more than two transfers.

Real-world constraints

The math is the easy part. A settlement feature people trust has to handle a few practical details.

• Use integer cents and deterministic rounding. Floating-point balances that sum to 0.0000001 will produce phantom one-cent transfers.
• Respect relationships. Simplification can ask someone to pay a person they never shared an expense with. Let groups turn it off, or restrict transfers to people who share at least one expense, and optimize within those constraints.
• Keep results stable. If one new €3 coffee reshuffles every transfer, people lose trust. Prefer solutions close to the previous settlement when adding small expenses.
• Settle one currency at a time. Convert to the group’s base currency at a recorded rate, or simplify each currency separately, and show the rate used.
• Explain the result. Show each person their net balance and why they are paying someone they did not expect. Transparency matters as much as the transfer count.

Inside a company the same logic applies to reimbursements: rather than colleagues paying each other back, net everything against the company and pay out once. That is how expense reimbursements for startups keep month-end simple.

Summary

Compute net balances in integer cents, then match the largest debtor with the largest creditor. That settles any group in at most n − 1 transfers and is optimal for most real receipts. When a group splits round amounts, or when every transfer counts, use the subset dynamic program to find the true minimum. For the human side of settling up, read why splitting the bill feels awkward.