How to settle multi-person debts in minimum transactions

Problem Statement

A group of friends frequently share expenses. You are given a list of transactions, where transactions[i] = [giver, receiver, amount] indicates that person giver lent amount to person receiver.

A person's net balance is the total amount they received minus the total amount they gave. To settle all debts, money must be transferred among the participants so that every person's net balance becomes zero.

Write a function to return the minimum number of transactions required to settle all debts.

Function Signature

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

Constraints

• 1 <= len(transactions) <= 1000
• transactions[i] = [giver, receiver, amount]
• giver != receiver
• 0 <= giver, receiver <= 100
• 1 <= amount <= 1000
• The number of people with non-zero net balances will not exceed 12.

Examples

Example 1

Input: transactions = [[0, 1, 10], [2, 0, 5]]
Output: 2
Explanation:
Person 0 gave 10 to person 1 and received 5 from person 2.
- Net balances:
  - Person 0: -10 + 5 = -5 (owes 5)
  - Person 1: +10 (is owed 10)
  - Person 2: -5 (owes 5)
Two transactions are required:
1. Person 0 pays 5 to Person 1.
2. Person 2 pays 5 to Person 1.

Example 2

Input: transactions = [[0, 1, 10], [1, 0, 1], [1, 2, 5], [2, 0, 5]]
Output: 1
Explanation:
- Person 0 net balance: -10 + 1 + 5 = -4 (owes 4)
- Person 1 net balance: 10 - 1 - 5 = +4 (is owed 4)
- Person 2 net balance: 5 - 5 = 0 (settled)
Only 1 transaction is needed: Person 0 pays 4 to Person 1.

Edge Cases to Consider

• All debts cancel out completely in the initial transactions (result is 0).
• Self-contained groups of debts that can be settled independently.
• People who appear in transactions but already have a net balance of 0.