Compute Balances and Minimize Settlements

Problem Statement

You are given a list of peer-to-peer transactions within a group. Each transaction is represented as a tuple (payer, payee, amount), indicating that payer gave amount dollars to payee.

Your task is to compute the net balance for each person and then find the minimum number of transactions required to completely settle all debts within the group.

A settlement is complete when every person's net balance becomes 0. People are allowed to send money to anyone in the group, even if they never transacted with each other initially.

Function Signature

def min_transfers_to_settle(transactions: list[tuple[str, str, int]]) -> int:
    pass

Input & Output Format

• Input: A list of tuples (payer, payee, amount) where payer and payee are strings representing person IDs, and amount is a positive integer.
• Output: An integer representing the minimum number of settlement transfers required.

Constraints

• 1 <= len(transactions) <= 10^4
• 1 <= amount <= 10^5
• The number of unique people with a non-zero net balance after aggregation is at most 14.
• No person transacts with themselves (payer != payee).

Examples

Example 1

Input: transactions = [
    ("Alice", "Bob", 10),
    ("Bob", "Charlie", 10)
]
Output: 1
Explanation:
Alice is net -10, Bob is net 0, Charlie is net +10.
Alice can directly transfer 10 to Charlie. Total transfers = 1.

Example 2

Input: transactions = [
    ("Alice", "Bob", 20),
    ("Alice", "Charlie", 20),
    ("Bob", "David", 30),
    ("Charlie", "David", 10)
]
Output: 3
Explanation:
Net balances:
- Alice: -40
- Bob: +20 - 30 = -10
- Charlie: +20 - 10 = +10
- David: +40

One optimal settlement sequence is:
1. Alice pays David 40
2. Bob pays Charlie 10
This requires 2 transfers? Wait: -40 + 40 = 0, -10 + 10 = 0. That actually takes only 2 transfers!
Output: 2

Edge Cases

• All initial transactions already balance out (e.g., A pays B 10, B pays A 10): Net balances are all 0, return 0.
• Disjoint subgroups of debt (e.g., {A, B} balance each other, {C, D} balance each other).