Optimal Account Balancing - Solution & Explanation

Problem Overview: You receive a list of transactions between people. Each transaction transfers money from one person to another. The goal is to settle all debts with the minimum number of additional transactions.

The key observation: instead of working with the original transactions, compute each person's net balance. Positive means they should receive money, negative means they owe money. The problem then becomes pairing these balances so that all accounts end at zero using the fewest transfers.

Approach 1: Backtracking on Net Balances (O(n!) time, O(n) space)

First build a balance array using an array. Iterate through transactions and update each person's net balance. Filter out zeros because they are already settled. Then apply backtracking: pick the first non‑zero balance and try settling it with every opposite‑signed balance that appears later in the list. For each pairing, transfer the amount, recurse, and restore the balance (classic DFS with backtracking). Pruning happens when identical balances appear or when a perfect cancellation occurs. This drastically reduces the search space and works well for the typical constraint of ≤12 people with non‑zero balances.

Approach 2: Bitmask Dynamic Programming (O(n * 2^n) time, O(2^n) space)

Another approach uses dynamic programming with bit manipulation. Each bitmask represents a subset of people whose balances we try to settle internally. Compute the total balance of each subset; if it equals zero, that subset can settle with size - 1 transactions. Use DP to combine smaller zero-sum subsets into larger ones and minimize transactions. The state dp[mask] stores the minimum transactions needed for that subset. Iterating over submasks allows merging valid groups efficiently.

The DP formulation transforms the problem into partitioning people into zero-sum groups. Each group requires exactly k - 1 transactions if it contains k people.

Recommended for interviews: Backtracking with balance reduction is the most common interview solution. It shows you understand debt compression and recursive search with pruning. Bitmask DP is more advanced and demonstrates strong skills with subset states and optimization, but many candidates default to the backtracking approach because it is easier to reason about during whiteboard interviews.