Compute minimal transfers to settle group expenses

Problem

A group of friends go on a trip and share expenses. Each expense is recorded as an object:

• payer (string): who paid the full amount
• amount (integer): total amount paid (assume in cents to avoid floating point)
• payees (string[]): the friends who should share this expense equally

Each payee owes an equal share of that expense. The payer may also appear in payees (meaning they also consume/share the expense).

Task

Given an array of such expenses, compute a set of money transfers between friends that settles all debts:

• After applying your transfers, every person’s net balance becomes 0 (no one owes/is owed).
• The transfers should be minimal in the sense of using the fewest number of payments/transactions possible.
• If multiple minimal answers exist, returning any one is acceptable.

Output format

Return an array of transfer objects:

• payer : the person who sends money (the debtor)
• amount : the amount sent (integer, in cents)
• payees : an array containing exactly one person who receives the money (the creditor)

Example transfer: { payer: "bob", amount: 1000, payees: ["alice"] } meaning “bob pays alice 1000 cents”.

Example

Input

[
  { payer: 'alice', amount: 4000, payees: ['bob', 'jess', 'alice', 'sam'] },
  { payer: 'jess', amount: 2000, payees: ['jess', 'alice'] }
]

Output (one valid minimal answer)

[
  { payer: 'bob', amount: 1000, payees: ['alice'] },
  { payer: 'sam', amount: 1000, payees: ['alice'] }
]

Notes / Constraints

• amount is divisible by payees.length (so equal splitting is exact).
• Names are case-sensitive strings.
• You may assume the input size is large enough that an efficient solution is expected.