Simplify Debts Between Group Members

Problem Given a group of people and a list of pairwise debts (who owes whom how much), settle everyone up using as few transactions as possible.

Input / Output

• Input: a list of transactions (from, to, amount).
• Output: the minimum number of transactions that bring every person's net balance to zero (extension: the actual transfer list).

Constraints

• Group sizes are small — typically at most ~12 distinct people — which hints that exponential search over subsets is intended.
• Every person ends net-positive (owed money), net-negative (owing), or zero. All net balances necessarily sum to 0.
• Anyone at a zero net balance drops out of the settlement entirely and must receive no transaction.

Example

• A owes B 10, B owes C 10 -> nets are A: -10, B: 0, C: +10 -> one transaction, A pays C 10. B vanishes from the settlement despite appearing in both original debts.
• Nets [-4, -3, +2, +2, +3]: greedy max-creditor/max-debtor matching needs 4 transactions, but the optimum is 3 — settle {-4, +2, +2} among themselves (2) and {-3, +3} directly (1). That gap is why greedy is not minimal.