Settle a Group Tab With the Fewest Possible Payments

A group of coworkers has been covering each other's lunch orders all month and wants to settle up once at the end. You're given a history of individual debts recorded between pairs of people, and you need to produce a list of payments that leaves everyone even.

Part 1 — Any valid settlement

Implement:

def settle_up(debts: list[tuple[str, str, int]]) -> list[tuple[str, str, int]]:
    """debts is a list of (debtor, creditor, amount): debtor owes creditor
    amount cents. The same pair may appear multiple times, in either direction.
    Returns a payment plan as (payer, payee, amount) triples, every amount positive,
    such that applying all of them brings every balance to zero."""

There's no limit on how many payments you return — any correct settlement is accepted here.

debts = [("alice", "bob", 1000), ("bob", "carol", 1000)]
settle_up(debts)   # e.g. [("alice", "carol", 1000)]: bob is owed exactly what he owes, so he drops out entirely

Part 2 — The fewest payments

Now implement settle_up_minimal, with the same signature, that returns a settlement using as few payments as possible. Fewer payments is strictly better; any minimal-length valid settlement is accepted.

Constraints and Clarifications

• Amounts are positive integers in cents. The same two people may owe each other in both directions across multiple recorded debts.
• A settlement payment may be between any two people, not only pairs that appear in the original debts list.
• Assume a modest group size (interview-sized, not thousands of people) for Part 2 — the minimal-payment version does not need to be polynomial-time.

Clarifying Questions

• Should floating-point amounts be supported, or are integer cents always guaranteed?
• Is a person who never appears in debts but ends up in a payment considered valid, or must every payer/payee have appeared in the input?
• For Part 2, is "fewest payments" the only objective, or should ties be broken by, say, preferring round amounts or specific people?

Part 1 — Any valid settlement

Every person's net position — total owed to them minus total they owe — is a single signed number. What property must these numbers have in total, and why?

With one list of people who owe and one list of people who are owed, can a single pass across both, settling the smaller amount each time, ever get stuck?

What This Part Should Cover

• Reducing the debt list to one net balance per person, and noting the balances must sum to zero
• A single pass matching debtors to creditors that always terminates with everyone at zero
• The number of payments this naturally produces, and why it's at most (people with nonzero balance) − 1

Part 2 — Minimizing payments

There is in general no shortcut that avoids trying different pairings — this is the same flavor of problem as partitioning a set of numbers into zero-sum groups, which is hard in general. Search, but don't repeat work.

What This Part Should Cover

• Why a locally greedy match (always pair the largest debtor with the largest creditor) can require more payments than necessary
• A backtracking search over who settles with whom next, with memoization on the current set of outstanding balances
• Why this is worst-case exponential, and why that's an acceptable trade-off for a small group