Problem statement

https://binarysearch.com/problems/Minimum-Number-of-Transfers-to-Settle-Debts/

Solution

Equal to Leetcode 0465 Optimal Account Balancing.

Complexity

Time is O(2^n * n), space is O(2^n).

Code

class Solution:
    def solve(self, edges):
        tmp = defaultdict(int)
        for a, b, m in edges:
            tmp[a] -= m
            tmp[b] += m
            
        debts = [val for val in tmp.values() if val != 0]
        n = len(debts)
        if n == 0: return 0
        
        dp = [(-float('inf'),float('inf'))] * (1<<n)
        dp[0] = (0, 0)
        for i in range(n): dp[1<<i] = (1, debts[i])
        
        for i in range(1, 1<<n):
            for j in range(n):
                if i & (1<<j):
                    parts, rest = dp[i ^ (1<<j)]
                    
                    if rest == 0 and dp[i][0] < parts + 1:
                        dp[i] = parts + 1, dp[1<<j][1]
                    if rest > 0 and dp[i][0] < parts:
                        dp[i] = parts, rest + dp[1<<j][1]
               
        return n - dp[-1][0]