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: return dfs(b[1:]) for i in range(1, len(b)): if b[i] == -b: return 1 + dfs(b[1:i] +  + b[i+1:]) ret =  for i in range(1, len(b)): if b[i] * b < 0: ret.append(dfs(b[1:i] + [b[i]+b] + b[i+1:])) return 1+min(ret) return dfs(balances)