Settle debts with minimal transactions

Question

You are given a list of debts among a set of people, expressed as triples (debtor, creditor, amount) (equivalently (payer, payee, amount)), where each amount is a positive integer. Return a set of settlement transfers (from, to, amount) that clears every participant's net balance, using the minimum possible number of transactions. If several optimal solutions exist, return any one of them.

1. Core algorithm. First reduce the raw debts to each person's net balance (total owed minus total owed-to-them). People whose net balance is zero are already settled and can be ignored. Then produce a sequence of transfers that zeroes out all remaining balances with the fewest transfers.
2. Multiple optimal answers. There can be many transfer sets of the same minimal size; any optimal one is acceptable.
3. Constraints / scale. Amounts are integers; assume up to about 20 distinct people in the basic version. Discuss how your approach behaves as the number of people N grows and as the debt graph becomes large or skewed (a few people owing/owed by many).
4. Large intermediate balances. Net balances can be large after consolidation; explain how you avoid overflow (e.g. 64-bit accumulators) and that summing all signed balances must equal zero.
5. Algorithm, correctness, and complexity. Describe your method (e.g. greedy lower bound, backtracking with pruning on net balances, or a subset/grouping formulation), prove correctness or give a justification, and analyze time and space complexity.