Settle Debts II
Debts arrive as (debtor, creditor, amount) triples: the debtor owes the creditor that amount. Return the minimum number of transfers that settles everyone. A transfer moves any amount from one person to another.
debts = [[0, 1, 10], [1, 0, 1], [1, 2, 5], [2, 0, 5]] => 1 (person 1 pays person 0 four; everyone else nets to zero)
Around 20 people can carry a nonzero balance. The general problem is NP-hard, so a search with good pruning is expected.
Hints
Hint 1
Only net balances matter: debtor −amount, creditor +amount. Anyone at zero drops out of the problem entirely.
Hint 2
A group of g people whose balances sum to zero settles internally in g − 1 transfers. So the answer is n − (the most disjoint zero-sum groups you can form).
Hint 3
Backtracking: settle balance i against each later balance of the opposite sign, recurse, and undo. Skipping a value you already tried at this level prunes most of the tree.