Optimal account balancing

class Solution:
    def __init__(self):
        self.res = math.inf
        self.person = None
        self.path = []
        self.debug = []

    def backtrack(self, start, curr):
        while  start < len(self.person) and self.person[start] == 0:
            start += 1
        if start == len(self.person):
            if curr < self.res:
                self.res = curr
                self.debug = self.path.copy()
        for i in range(start, len(self.person)):
            if self.person[start] * self.person[i] < 0:
                self.person[i] += self.person[start]
                self.path.append(i)
                self.backtrack(start + 1, curr + 1)
                self.path.pop()
                self.person[i] -= self.person[start]

    def minTransfers(self, transactions: List[List[int]]) -> int:
        person = collections.defaultdict(int)
        for _from, _to, amount in transactions:
            person[_from] -= amount
            person[_to]   += amount
        self.person = list(person.values())
        self.backtrack(0, 0)
        # print(self.debug)
        return self.res

Optimal Account Balancing

Difficulty: Hard

You are given an array of transactions transactions where transactions[i] = [fromi, toi, amounti] indicates that the person with ID = fromi gave amounti $ to the person with ID = toi.

Return the minimum number of transactions required to settle the debt.

 

Example 1:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

Example 2:

Input: transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Output: 1
Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.
Therefore, person #1 only need to give person #0 $4, and all debt is settled.

 

Constraints:

  • 1 <= transactions.length <= 8
  • transactions[i].length == 3
  • 0 <= fromi, toi < 12
  • fromi != toi
  • 1 <= amounti <= 100