Say some 20 people go to a shop and everyone buys something. When it comes to paying, 5 of them pay the complete amount of 10,000$ split unequally between them. Since everyone bought different things they all owe different amounts to the payers. Now there are multiple ways the payers can clear the balances with the payees precisely 20 to the power 20. My question is on what technical basis should the payers and payees contact each other for clearance? All the solutions can not be equally good, or are they?One of the ways of clearing would be to find payers and payees with equal amount so that they can cancel out each other thus reducing the total number of transfers.UPDATE:People can transfer arbitrary amounts to anyone.Minimizing total number of transfers is the main goal. A payee can not pay an amount greater that what he owes and become secondary payer.The output should be a list of suggested transfers. A suggested transfer would look like this {FromUser: a, ToUser: b, ClearanceAmount: 100}The payers don't know who holds their debt.The payees debt can be split across multiple payers.The payees knows how much each payer paid from the total amount.
Best way to clear balances between payers and payees
algorithms
This is a generalization of the subset sum problem.In the simple case, where there are two payers, it is identical to the subset sum problem.  Either there is subset of debts exactly equal to the amount payed by one payer, or one payment must be split between the two payers.The subset sum problem is NP complete, so there is no fast solution.