# Easy backtracking + greedy solution with explanation (Python, Accepted)

• Just to share a backtracking + greedy solution. The Python implementation was accepted.

First, compute net profit for every person.

``````For transactions:
[0, 1, 10]
[2, 0, 5]

Person, netProfit
0,         -5
1,         10
2,         -5
``````

Then, preserve unsettled people only whose net profit != 0.

Now backtrack to maintain the unsettled range [startIdx :]. Person X is settled means that X's net profit becomes 0 after one transaction with another unsettled person Y. Obviously, the amount of this transaction must be equal to X's net profit in their absolute values for X to be settled.

Note that there may be some settled people within the unsettled range [startIdx :]. For instance, if someone within this unsettled range happened to be precisely closed out by someone else in the settled range.

The greedy condition is precise closing-out (two people's net profit sum = 0). Since precise closing-out reduces number of unsettled people by 2 rather than 1, it is in fact the optimal condition.

If greedy condition cannot be found, try non-greedy solutions.

Comments can be found in the following implementation.

``````class Solution(object):
def minTransfers(self, transactions):
# Compute net profit for every person.
personNetProfit = dict()
for lender, borrower, amount in transactions:
personNetProfit[lender] = personNetProfit.get(lender, 0) - amount
personNetProfit[borrower] = personNetProfit.get(borrower, 0) + amount
# Preserve unsettled people only.
netProfit = []
for amount in personNetProfit.values():
if amount != 0:
netProfit.append(amount)
return self.traverse(netProfit, 0, 0)

def traverse(self, netProfit, startIdx, numTrans):
# Skip settled people.
while startIdx < len(netProfit) and netProfit[startIdx] == 0:
startIdx += 1
if startIdx + 1 >= len(netProfit):
return numTrans
else:
for i in range(startIdx + 1, len(netProfit)):
# Greedy condition.
if netProfit[startIdx] + netProfit[i] == 0:
netProfit[i] += netProfit[startIdx]
minNumTrans = self.traverse(netProfit, startIdx + 1, numTrans + 1)
netProfit[i] -= netProfit[startIdx]
return minNumTrans
minNumTrans = sys.maxint
for i in range(startIdx + 1, len(netProfit)):
# Non-greedy condition for possible closing out in the future.
if netProfit[startIdx] * netProfit[i] < 0:
netProfit[i] += netProfit[startIdx]
minNumTrans = min(minNumTrans, self.traverse(netProfit, startIdx + 1, numTrans + 1))
netProfit[i] -= netProfit[startIdx]
return minNumTrans
``````

• Thanks for the idea of greedy shortcut. This is my shorter version:

``````def minTransfers(self, transactions):
counter = collections.Counter()
for f, t, m in transactions:
counter[f] -= m
counter[t] += m
balances = counter.values()
def dfs(b):
if not b:
return 0
if not b[0]:
return dfs(b[1:])
for i in range(1, len(b)):
if b[i] == -b[0]:
return 1 + dfs(b[1:i] + [0] + b[i+1:])
ret = []
for i in range(1, len(b)):
if b[i] * b[0] < 0:
ret.append(dfs(b[1:i] + [b[i]+b[0]] + b[i+1:]))
return 1+min(ret)

return dfs(balances)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.