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
```