465. Optimal Account Balancing
Given a list of transactions as a list of triplets: (a, b, c), meaning a give b an amount of c dollars. Now we want to settle all the debt with the minimum number of transactions. For example, (0, 1, 5) (1, 2, 5) can be settled with one transaction (2, 0, 5). We only need return one integer: the minimum number of transactions needed.
We don't need to consider the transaction graph. Imagine during settling the debt, everyone who need to return money to others just put those money in a pool. The people who should receive money from others just take from that pool. After this, all debt are settled without knowing the original transaction graph.
First, we calculate how much money each person owns (can be positive or negative). Then, we just use DFS to settle the debt. One person will return all his debt to another person. The DFS will search every choice of choosing the person. Then we start to search the choices of the next person.
One concern is, what if the optimal solution is not for a person returning all his debt to another person, but returning his debt to multiple people? We can always find an equivalent case in our search space. For example, if the optimial solution is for a return money to b and to c. We can find a equivalent in our search space for a to return all the money to b, and b will return the extra amount to c. The 2 solutions both take 2 transactions to fiinsh.
import collections class Solution: def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self.num_people = 0 self.debt =  def cal_debt(self, transactions): temp = collections.defaultdict(lambda : 0) for transaction in transactions: temp[transaction] += transaction temp[transaction] -= transaction for key, value in temp.items(): self.debt.append(value) self.num_people = len(self.debt) def dfs(self, current_id): while (current_id < self.num_people and self.debt[current_id] == 0): current_id += 1 if current_id >= self.num_people: return 0 ret = self.num_people * self.num_people for next_id in range(current_id + 1, self.num_people): if self.debt[current_id] * self.debt[next_id] < 0: self.debt[next_id] += self.debt[current_id] ret = min(ret, self.dfs(current_id + 1) + 1) self.debt[next_id] -= self.debt[current_id] return ret def minTransfers(self, transactions: List[List[int]]) -> int: self.cal_debt(transactions) return self.dfs(0)