465. Optimal Account Balancing

[box-lin]

Time: O(n!)
Space: O(n)

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        dep = [0] * 12
        for x, y, amount in transactions:
            dep[x] -= amount
            dep[y] += amount
        
        def dfs(i):
            while i < len(dep) and dep[i] == 0: 
                i += 1
            if i >= len(dep):
                return 0
            minop = math.inf
            for j in range(i+1, len(dep)):
                if dep[i] * dep[j] < 0:
                    # we settle up dep[i] by put dep[i] to dep[j]
                    dep[j] += dep[i]
                    minop = min(minop, dfs(i+1) + 1)
                    dep[j] -= dep[i]
            return minop
        return dfs(0)