​LeetCode刷题实战465：最优账单平衡

示例 1：

输入：
[[0,1,10], [2,0,5]]
输出：
2

解释：
人 #0 给人 #1 共计 10 美元。
人 #2 给人 #0 共计 5 美元。

需要两次交易。一种方式是人 #1 分别给人 #0 和人 #2 各 5 美元。

示例 2：

输入：
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]
输出：
1

解释：
人 #0 给人 #1 共计 10 美元。Person #0 gave person #1 $10.
人 #1 给人 #0 共计 1 美元。Person #1 gave person #0 $1.
人 #1 给人 #2 共计 5 美元。Person #1 gave person #2 $5.
人 #2 给人 #0 共计 5 美元。Person #2 gave person #0 $5.

因此，人 #1 需要给人 #0 共计 4 美元，所有的债务即可还清。

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        from collections import defaultdict
        person = defaultdict(int)
        for x, y, z in transactions:
            person[x] -= z
            person[y] += z
        # 账号
        accounts = list(person.values())
       
        res = float("inf")

        def dfs(i, cnt):
            nonlocal res
            # 全局变量退出递归
            if cnt >= res: return 
            # 账号为0不考虑
            while i < len(accounts) and accounts[i] == 0: i += 1
            # 遍历完
            if i == len(accounts):
                res = min(res, cnt)
                return
            for j in range(i + 1, len(accounts)):
                if accounts[i] * accounts[j] < 0:
                    accounts[j] += accounts[i]
                    dfs(i + 1, cnt + 1)
                    accounts[j] -= accounts[i]

        dfs(0, 0)
        return res