Problem description:

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:

1
2
3
4
5
6
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:

1
2
3
4
5
6
7
8
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 #0 only need to give person #1 $4, and all debt is settled.

Constraints:

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

Solution:

First, compute net profit for every person.

1
2
3
4
5
6
7
8
9
10
11
12
For transactions:
[0, 1, 10]
[2, 0, 5]
[2, 3, 3]
[1, 4, 5]

Person,  balance
0,        -10+5 = -5
1,         10-5 = 5
2,        -5-3  = -8
3,         3
4,         5

Then pass the balance values to do DFS

  • first try to find if there’s any -balance[0] that could finish in one transaction
  • if can not, then add balance[0] into another balance[i]. Since we want to find the minimum number of transaction, we could use a variable to record the res.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[-5, 5, -8, 3, 5]
--------
find idx:1 have -balance 5, remaining: [0, -8, 3, 5]
------
balance[0] = 0, remaining: [-8, 3, 5]
can't find same -balance, settle the balance to others
add to idx:1:-5 , remaining: [0, 5]
find idx:1 have -balance 5, remaining: [0]
------
balance[0] = 0, remaining: []
add to idx:2:-3 , remaining: [3, 0]
find idx:1 have -balance -3, remaining: [0]
------
balance[0] = 0, remaining: []
------
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        # build transaction with counter
        counter = Counter()
        for f,t,m in transactions:
            counter[f] -= m
            counter[t] += m
        balances = list(counter.values())
        # dfs to find minimum pair
        # takes balance array as input to do dfs
        def dfs(balance):
            if not balance:
                return 0
            if not balance[0]:
                return dfs(balance[1:])
            
            # balance[0] has balance need to settle, check if someone happen to have -balance 
            for i in range(1, len(balance)):
                if balance[i] == -balance[0]:
                    return 1+ dfs(balance[1:i]+ [0]+ balance[i+1:])
            
            # can't find same -balance
            # settle balance[0] to separate balance, use dfs to find smaller one
            # notice we only want to find in different sign
            res = float('inf')
            for i in range(1, len(balance)):
                if balance[i]*balance[0] < 0: # different sign
                    res = min(res, dfs(balance[1:i]+ [balance[i]+balance[0]]+ balance[i+1:]))
            return 1+ res
        return dfs(balances)

time complexity: $O()$
space complexity: $O()$
reference:
related problem: