Minimum Number of Transfers to Settle All Debts in a Group

A group of people have lent money to each other. Each record transactions[i] = [x, y, amount] means that person x gave amount to person y. The group now wants to settle up with new transfers so that, counting both the original transactions and the new transfers, every person has given exactly as much as they have received.

Return the minimum number of new transfers needed.

Function Signature

def min_transfers(transactions: list[list[int]]) -> int:

Rules

• A person's net balance is the total amount they gave minus the total amount they received. All debts are settled when every person's net balance is 0.
• A new transfer moves a positive integer amount from one person to a different person. Any person may send or receive any number of new transfers, and transfers are not limited to pairs of people who appear together in transactions.
• People are identified only by their integer IDs. A person who appears in no transaction is not involved.
• Return 0 if every net balance is already 0.

Constraints

• 1 <= len(transactions) <= 8
• transactions[i] == [x, y, amount] with 0 <= x <= 11, 0 <= y <= 11, x != y and 1 <= amount <= 100
• Every sum involved fits in a 32-bit signed integer.

Examples

Example 1

Input: transactions = [[0, 1, 10], [2, 0, 5]]
Output: 2

Person 0 gave 10 and received 5, so they are owed 5. Person 1 received 10 and owes 10. Person 2 gave 5 and is owed 5. Person 1 pays 5 to person 0 and 5 to person 2. A single transfer cannot settle three nonzero balances.

Example 2

Input: transactions = [[0, 1, 10], [1, 0, 1], [1, 2, 5], [2, 0, 5]]
Output: 1

Person 0 gave 10 and received 6, so they are owed 4. Person 1 gave 6 and received 10, so they owe 4. Person 2 gave 5 and received 5, so they are already settled. One transfer of 4 from person 1 to person 0 settles everything.

Example 3

Input: transactions = [[0, 1, 5], [1, 0, 5]]
Output: 0