LeetCode: 465. Optimal Account Balancing

First, we look through all the transactions and check how much money(or debt) each one has. Array self.money is storing that information, and we excluded the ones who don't have any money or debt.

Next, let's define "helper(self, indexs)" as our goal function. It will return 'min # of transactions needed'. Here, we take indexes (tuple type) as the parameter of the function so that we can easily store returned results in a "self.dp" dictionary.

Now, the most important part: drawing out the recursion equation.

--> helper(indexes) = min(helper(rest) + k - 1), for all combinations of size k that add up to zero.

rest: indexes - indexes of a certain combination of size k that add up to zero.

<Example>

self.money: [3, -1, -2, 4, 1, 3]

helper((0, 1, 2, 3, 4, 5))

index 0, 1, 2 add up to zero (as 3 -1 -2 = 0), so k = 3 and rest is (3, 4, 5). 

from itertools import combinations
class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        money = [0] * 21
        for f, t, m in transactions:
            money[f] -= m
            money[t] += m
        self.money = [m for m in money if m != 0]
        idxs = tuple([i for i in range(len(self.money))])
        self.dp = {}
        return self.helper(idxs)
        
    def helper(self, idxs):
        if not idxs:
            return 0
        if idxs in self.dp:
            return self.dp[idxs]
        
        ret = len(idxs) - 1
        for k in range(2, len(idxs)//2+1):
            for temp in combinations(idxs, k):
                if sum([self.money[i] for i in temp]) == 0:
                    rest = tuple(set(idxs) - set(temp))
                    ret = min(ret, self.helper(rest) + k - 1)
        self.dp[idxs] = ret
        return ret

 

from itertools import combinations
import functools

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        money = [0] * 12
        for f, t, m in transactions:
            money[f] -= m
            money[t] += m
        self.money = [m for m in money if m != 0]
        idxs = tuple([i for i in range(len(self.money))])
        return self.helper(idxs)
    
    @lru_cache()
    def helper(self, idxs):
        if not idxs:
            return 0
        ret = len(idxs) - 1
        for k in range(2, len(idxs)//2+1):
            for temp in combinations(idxs, k):
                if sum([self.money[i] for i in temp]) == 0:
                    rest = tuple(set(idxs) - set(temp))
                    ret = min(ret, self.helper(rest) + k - 1)
        return ret