Problem statement

https://leetcode.com/problems/optimal-account-balancing/

Solution

There is bit-dp solution, where the approach is to find groups of elements with sum equal to zero: we need to find the maximum number of subsets we can partition, such that sum in each subset is equal to zero. This is similar to problem 0698: Partition to $K$ Equal Sum Subsets. In dp[i] we keep two numbers: maximum number of parts so far and sum of all elements given bitmask i.

Complexity

Time complexity of this approach is $O(2^n n)$, space complexity is $O(2^n)$.

class Solution:
   class Solution:
    def balanceGraph(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]