⚡Flashcard Drill➔
NeetCode #708LC-465Hard1-D Dynamic Programming
← Back to All Problems

#708 · #465 · Optimal Account Balancing(最优账单平衡)

📌 Problem Statement & Constraints

Given transactions, where transactions[i] = [from, to, amount] means from paid to that amount, return the minimum number of transactions needed to settle all debts. Constraints: 1 <= transactions.length <= 8, 0 <= from, to < 12, 1 <= amount <= 100.

💡 Core Algorithmic Approaches

  1. First compute each person's net balance: positive if they are owed money, negative if they owe.
  2. People with a zero net balance are already settled and can be ignored.
  3. Run a DFS over the non-zero balances: take the first unsettled person and try matching them against every other person with the opposite sign.
  4. The minimum number of transfers is the shallowest DFS branch that clears all balances.

💻 Benchmark Python3 Implementation

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        from collections import defaultdict
        bal = defaultdict(int)
        for f, t, a in transactions:
            bal[f] -= a
            bal[t] += a
        debts = [v for v in bal.values() if v != 0]

        def dfs(start: int) -> int:
            while start < len(debts) and debts[start] == 0:
                start += 1                 # skip settled people
            if start == len(debts):
                return 0
            best = float("inf")
            for i in range(start + 1, len(debts)):
                if debts[i] * debts[start] < 0:     # opposite signs can settle
                    debts[i] += debts[start]
                    best = min(best, 1 + dfs(start + 1))
                    debts[i] -= debts[start]        # backtrack
            return best

        return dfs(0)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n!) worst case, but the number of non-zero balances is at most 12 and the search is pruned heavily.
💾 Space Complexity
O(n): the balances and the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting to backtrack: the debts[i] update must be undone before trying the next candidate.
  • Matching only same-sign balances: the guard debts[i] * debts[start] < 0 ensures a transfer reduces both magnitudes.
  • Skipping zero balances only once: the while loop must re-skip after every recursion, which the start + 1 argument handles.
  • Greedily pairing the largest debtor with the largest creditor: that heuristic can use more transactions than the optimum.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems