Optimal Account Balancing Python Solution

lcpy gen -n 465   # by problem number
lcpy gen -s optimal_account_balancing   # by problem name

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

Input: transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Output: 1
Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.
Therefore, person #1 only need to give person #0 $4, and all debt is settled.

class Solution:
    # Time: O(k! ) worst case over k non-zero balances
    # Space: O(k)
    def min_transfers(self, transactions: list[list[int]]) -> int:
        balances: dict[int, int] = {}
        for sender, receiver, amount in transactions:
            balances[sender] = balances.get(sender, 0) - amount
            balances[receiver] = balances.get(receiver, 0) + amount
        debts = [v for v in balances.values() if v != 0]

        def settle(start: int) -> int:
            while start < len(debts) and debts[start] == 0:
                start += 1
            if start == len(debts):
                return 0
            best = len(debts)
            seen: set[int] = set()
            for i in range(start + 1, len(debts)):
                if debts[i] * debts[start] < 0 and debts[i] not in seen:
                    seen.add(debts[i])
                    debts[i] += debts[start]
                    best = min(best, 1 + settle(start + 1))
                    debts[i] -= debts[start]
            return best

        return settle(0)