Fewest Transfers to Settle Balances

hard

Backtracking Bit Manipulation Dynamic Programming

A group-payments feature lets friends record who paid for what during a trip. At the end, the app suggests how to settle up, and every bank transfer is friction (and sometimes a fee), so it should suggest as few transfers as possible.

People are numbered 0 to 11. transactions[i] = [from, to, amount] means person from paid amount on behalf of person to, so to owes from that amount. Debts add up and cancel out: if Ana owes Ben 10 and Ben owes Ana 4, Ana simply owes Ben 6.

A transfer moves any whole amount from one person to another. Return the minimum number of transfers after which nobody owes anybody anything.

Example

transactions = [[0,1,10],[2,0,5]]. Person 1 owes person 0 ten, and person 0 owes person 2 five. Overall, person 0 is owed 5, person 1 owes 10, and person 2 is owed 5. Two transfers settle it: person 1 sends 5 to person 0 and 5 to person 2. One transfer cannot, since three people have non-zero balances. The answer is 2.

Example 1

Input

[
  "[[0,1,10],[2,0,5]]"
]

Output

Explanation. The example.

Example 2

Input

[
  "[[0,1,10],[1,0,1],[1,2,5],[2,0,5]]"
]

Output

Explanation. Debts in a circle mostly cancel out: only one transfer is left.

Example 3

Input

[
  "[[0,1,5],[1,0,5]]"
]

Output

Explanation. Everyone is already even.

Example 4

Input

[
  "[[0,1,5],[1,2,5],[2,3,5]]"
]

Output

Explanation. A chain collapses to its two ends.

Example 5

Input

[
  "[[0,1,3],[2,3,4]]"
]

Output

Explanation. Two separate debts need two transfers.

Example 6

Input

[
  "[[0,4,3],[1,5,3],[2,4,2],[3,5,1],[3,6,3]]"
]

Output

Explanation. Seven balances: the best split uses three groups.

Example 7

Input

[
  "[[0,1,6],[0,2,3],[3,1,5],[3,4,4]]"
]

Output

Explanation. No smaller group settles on its own, so five balances need four transfers.

Example 8

Input

[
  "[[0,3,9],[1,3,4],[2,4,4],[5,6,7],[5,7,2],[8,6,3],[9,7,1],[10,11,6],[11,9,2]]"
]

Output

Explanation. Twelve people with unequal balances.

Example 9

Input

[
  "[[0,1,1],[1,2,1],[2,0,1]]"
]

Output

Explanation. A perfect circle.

Example 10

Input

[
  "[[0,1,4],[2,3,4],[4,5,4],[1,2,2],[3,4,2],[5,0,2]]"
]

Output

Explanation. Three pairs that each cancel exactly.

Follow-up: The app has to explain its suggestion: "Ana pays Ben 6". Extend your solution to return the transfers themselves, and argue why a group whose balances add up to zero can always be settled with one fewer transfer than it has members.

Constraints:

- `1 <= transactions.length <= 50` - `transactions[i].length == 3` - `0 <= from, to <= 11`, and `from != to` - `1 <= amount <= 100`

Views: 3