465. Optimal Account Balancing

几个层面的理解：

balances array 记录每个人的balance, 具体每个balance对应的personId并不重要
对于N个人的group, 最多需要N-1次transactions
- 如何定义一个valid group：group内balance和为0
- 如果能分成M groups，那么最终需要的transactions是N-M 所以这个问题就变成了找出最大的M such that total balance in each group is O

如何解释helper()的backtracking得到的是最优解？没找到一个靠谱的解读，我的理解是每一次balances[i] += balances[cur]就是试图把i和cur放入一个group. 在backtracking过程中去发现最优分组

time complexity: T(N) = N * T(N-1) = N!

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        transactionMap = collections.defaultdict(int)
        for f, t, m in transactions:
            transactionMap[f] -= m
            transactionMap[t] += m
        
        balances = []
        for balance in transactionMap.values():
            if balance:
                balances.append(balance)
        
        def helper(cur):
            while cur < len(balances) and balances[cur] == 0:
                cur += 1
            
            if cur == len(balances):
                return 0
            
            minTrans = float("inf")
            for i in range(cur+1, len(balances)):
                if balances[cur] * balances[i] < 0: 
                    balances[i] += balances[cur]
                    minTrans = min(minTrans, helper(cur+1) + 1)
                    balances[i] -= balances[cur]
            
            return minTrans

465. Optimal Account Balancing - cocoder39/coco39_LC GitHub Wiki