A group of friends shares costs on a trip. Each entry [payer, other, amount] in transactions means payer paid amount on behalf of other, so other owes payer that much. People are numbered 0 to 15.
At the end of the trip they settle up. A transfer is one payment of any amount from one person to another. Write min_transfers(transactions) -> int that returns the fewest transfers that leave everyone even.
Each person's balance is what they paid for others minus what others paid for them. A positive balance means they are owed money, a negative one means they owe it. Everyone is even once the transfers bring every balance to zero. The transfers don't have to follow the original entries: anyone may pay anyone.
min_transfers([[0, 1, 30], [1, 2, 30]])
# 1 (balances 0: +30, 1: 0, 2: -30; person 2 pays person 0 directly)
min_transfers([[0, 3, 7], [1, 4, 4], [2, 4, 2], [2, 0, 1]])
# 3 (balances +6, +4, +3, -7, -6: person 4 pays 0 six; person 3 pays 1 four and 2 three)
min_transfers([[0, 1, 5], [1, 2, 5], [2, 0, 5]])
# 0 (everyone paid 5 and had 5 paid for them)
In the second example, always settling the biggest debt against the biggest credit takes 4 transfers: 0 gets 6 from 3, then 1 gets 4 from 4, then 2 gets 2 from 4 and 1 from 3.
Constraints:
1 <= len(transactions) <= 1000.0 <= payer, other <= 15andpayer != other.1 <= amount <= 10^5.- ⭐ Bonus: settling one person at a time and trying every partner (backtracking) is fine for up to about 10 people with a non-zero balance. A speed test with 16 such people earns a star in about O(2^m · m), where
mis the number of people whose balance isn't zero.
Show hint
After working out the balances, people at zero drop out. If g people's balances add up to zero, they can settle among themselves in g - 1 transfers, and a group that sums to zero can never do it in fewer. So you want to split the m people into as many zero-sum groups as possible. With m <= 16, you can afford to look at every subset.