465. Optimal Account Balancing - Detailed Explanation

Problem Statement

Definition: We have a list of transactions, where each transaction is represented as a triple [x, y, z] meaning person x gave person y an amount of $z. Our goal is to determine the minimum number of transactions required to settle all debts among these people. In other words, we want to balance the accounts so that everyone’s net debt or credit becomes zero, using the least number of money transfers between individuals.

Key Points:

• A “settling transaction” means one person pays another person some amount of money to offset their debt. We want to minimize how many such transactions occur.
• Person IDs are not guaranteed to be contiguous or in order (e.g., you might have persons with IDs 0, 2, 6, etc.).
• If no one owes anything net (all accounts are already balanced), the result is 0 because no transactions are needed.

Constraints:

• 1 <= transactions.length <= 8 – At most 8 transactions are given as input.
• Each transaction is of the form [from, to, amount] with:
  • 0 <= from, to < 12 (ID range).
  • from != to (no self-transactions).
  • 1 <= amount <= 100 (positive amounts only).
• The total number of people involved can be up to 12 (IDs 0 through 11). Due to the small input size, exhaustive or brute-force approaches are feasible.

Example 1:

Input: transactions = [[0,1,10], [2,0,5]]
Output: 2

Explanation: Person #0 paid $10 for person #1, and person #2 paid $5 for person #0. To settle up, two transactions are required. One optimal way is for person #1 to pay $5 to person #0 and $5 to person #2. After these 2 transactions, all debts are settled (person #0 gets back $5 from #1 and $5 from #2, person #1 has paid out $10 total, person #2 gets back $5).

Example 2:

Input: transactions = [[0,1,10], [1,0,1], [1,2,5], [2,0,5]]
Output: 1

Explanation: The net debts after all given transactions are calculated as follows: person #0 ends up owing $4, person #1 ends up being owed $4, and person #2’s balance is $0 (we will show how to calculate these balances in the next sections). Therefore, one transaction — person #1 paying $4 to person #0 — is enough to settle all debts. After that single transaction, everyone’s balance becomes zero.

Hints

• Calculate Net Balances: A crucial insight is that the order of given transactions doesn’t matter – what matters is each person’s net balance (how much they owe or are owed in total). You can compute an array or map of balances where balance[i] is how much person i should receive (positive) or pay (negative) overall. This is done by summing up all transactions for each person (add amount for money received, subtract for money given). Once you have net balances, the original list of transactions can be disregarded for solving the rest of the problem.

• Ignore People with Zero Balance: Any person whose net balance is 0 can be removed from consideration. They neither owe nor are owed anything, so they don’t need to be involved in any settling transactions.

• Debtors and Creditors: After computing net balances, you will have a list of people who owe money (negative balance) and people who should receive money (positive balance). Our task reduces to matching debtors with creditors to clear all debts. Each settling transaction can reduce the number of people with non-zero balance by at least one (because one debtor or one creditor’s balance will become zero or closer to zero).

• Optimal Strategy – Combine Debts: To minimize transactions, try to combine debts whenever possible. For example, if person A owes $50 and there are two people B and C who are each owed $25, it might be optimal for A to pay B and C directly (two transactions) rather than having intermediate transactions. Always consider if one transaction can settle multiple original debts by paying off one person who can then pay another (this happens naturally when we look at net balances).

• Recursive Exploration: A backtracking (depth-first search) approach is promising: pick one person with a debt and try settling that debt with various other people, recursively solving the smaller subproblem for the remaining people. Prune searches that are clearly not optimal (for instance, if a debt can be exactly matched with a credit, that path should be taken first as it likely leads to fewer transactions).

• Use Memoization or Bitmask DP: Because the number of people with non-zero balance is limited (at most 12, usually fewer after ignoring zeros), we can use memoization to cache states we’ve computed. Each state can be represented by the list of current balances (or a bitmask representation of which balances are settled). This prevents re-computation of the same configurations of debts and credits.

Approaches to Solve the Problem

Brute Force Solution

A straightforward brute force approach would involve simulating all possible ways to settle the debts, then picking the way with the fewest transactions. In practice, this means considering every possible sequence of transactions among people until all balances become zero. However, this approach is extremely impractical because the number of possible sequences grows explosively with the number of people.

• How it might work: We could take any two people where one owes money and one is owed money, and perform a transaction between them (of some amount), then repeat this process until everyone is settled. For example, if A owes B and C, A could pay B first or C first (different order), and could even choose to pay part of the debt in one transaction and the rest in another. A brute force algorithm would branch out into all these possibilities.

• Why it’s infeasible generally: Without any strategy to limit choices, we would explore permutations of transactions and partial payments. Even for a small number of people, this search space is huge. For instance, if you have n people with outstanding balances, there are many ways to pair them up and settle amounts. The time complexity in the worst case would be super-exponential (factorial-like growth or worse).

• Small Constraint Saving Grace: The given constraints (max 8 transactions, up to 12 people) are small enough that a brute force might technically run, but we still want to optimize to avoid unnecessary computations. This is why we refine the brute force into a smarter backtracking approach.

Backtracking Approach

A backtracking solution systematically explores possible transactions but prunes away redundant or impossible paths, making it much more efficient than naive brute force. The idea is to resolve one person’s balance at a time, reducing the problem step by step. This approach is guaranteed to find the optimal solution given the small input size.

Steps of the Backtracking Solution:

1. Compute Net Balances: Use the input transactions to calculate each person’s net balance. For each [from, to, amount], subtract amount from from’s balance and add amount to to’s balance. For example, if we have transactions [[0,1,10],[2,0,5]] (from Example 1), the net balances would be: person 0 = -5 (paid $5 more than received), person 1 = +10 (received $10 more than paid), person 2 = -5. These net balances represent how much each person owes (negative) or is owed (positive).

2. Filter Zero Balances: Remove any entries that are zero, because those people don’t need to do anything. In our example, no one had a zero net balance initially (all three were non-zero). In Example 2, person #2’s net balance would compute to 0 (they gave and received $5), so person #2 can be ignored for debt-settlement purposes, leaving just person #0 and #1 to consider.

3. Recursively Settle Debts: Pick a person with a non-zero balance (say the first in the list). Try to settle this person’s balance by pairing them with another person:

   • Find another person with the opposite sign balance (one owes money, the other is owed money). Transfer money between these two to settle one of them completely. In practice, you add the balances together: one of them will go to zero. For example, if person A has -5 and person B has +10, you can have B pay A $5. Then person A’s balance becomes 0 (debt settled) and person B’s balance becomes +5 (still needs to receive $5 more from someone).

   • Record that as one transaction and then recursively handle the remaining balances (ignoring the now-settled person).

   • Explore different pairings of the chosen person with all possible counterparts and take the minimum transactions outcome.

4. Prune and Optimize:

   • If you find a pairing that exactly cancels out one person’s debt with another’s credit (e.g., one owes $X, another is owed $X, so one transaction can clear both), that path is likely optimal for that pair. You can break out of trying other pairings for that particular person because any other pairing would either use more transactions or just be a reordering of the same debts.
   • Also, skip over any intermediate cases where after a transaction a person’s balance becomes zero, immediately move to the next person without trying to pair the now-zero balance with others (this avoids redundant computations).

Using backtracking in this way drastically limits the search space. We always eliminate at least one person’s debt in each recursive step (one person gets settled to zero balance), so the depth of recursion is at most the number of people with non-zero balance. Additionally, by always matching opposite signs and stopping early on exact cancellations, we avoid exploring symmetric cases multiple times.

Correctness: The backtracking approach tries all meaningful combinations of settlements. Because it explores depth-first, it will eventually find an arrangement with the minimum number of transactions. It effectively treats the problem as an assignment of debts to credits and finds the smallest set of pairings that cover all balances.

Bitmasking and Optimized Approaches

For even more optimization, especially to avoid re-computation of similar states, we can use bitmasking and dynamic programming (DP). The idea is to use a bit mask to represent a subset of people (or balances) and use DP to figure out the minimum transactions needed for that subset.

Bitmask DP Idea: Suppose we have n people with non-zero balances. We can assign each person an index from 0 to n-1. A bitmask of length n (using an integer where the i-th bit corresponds to person i) can represent any subset of these people. For example, if n=3 (persons A, B, C), then a mask 101 (in binary) might represent the subset {A, C}. We then define a DP state as dp[mask] = minimum transactions needed to settle all balances for the subset of people indicated by mask. The final answer we want is dp[(1<<n) - 1], which corresponds to all people.

How the DP is computed:

• Base Case: dp[0] = 0 (no people means no transactions needed).

• Transitions: For any subset mask, we try to split it into two smaller parts that can settle debts among themselves. One clever approach is:

  • Pick a subset s of mask (i.e., s is a submask of mask) that has a total sum of balances = 0. If a group of people’s balances sum to zero, they can in principle settle all debts among themselves without needing anyone outside the group. In that case, the number of transactions needed within that group is (number of people in s) - 1 (at minimum, they can arrange themselves in a cycle or chain to settle with one fewer transaction than people).
  • We can then solve the remaining people in mask \ s separately. So one candidate for dp[mask] is dp[s] + dp[mask ^ s]. But since dp[s] (where sum of s is zero) would be (|s| - 1) by definition of optimal settling within that group, we might directly use that.
  • We take the minimum over all such zero-sum splits of mask.

• Example of DP reasoning: If we have a mask representing people {A, B, C} and their balance sum is zero, then dp[ABC] could be 2 (if A, B, C can settle in 2 transactions, for instance by a cycle). But if no convenient zero-sum subset of {A, B, C} exists except the whole set, the DP would try smaller masks. Perhaps person A and B together have zero sum (so dp[AB] = 1 transaction) and C alone is zero (dp[C]=0), then dp[ABC] = dp[AB] + dp[C] = 1 + 0 = 1 transaction. (This scenario is hypothetical – typically if A and B sum to zero, it means one owes the other directly and that’s 1 transaction).

Another optimized approach is to use memoization with recursion. As we attempt different combinations in a backtracking solution, we store the results of subproblems we have solved (for example, the minimal transactions needed for a particular set of remaining balances). A convenient way to key the memo is to use a bitmask of which people are still unsettled or even a tuple of sorted balances. By doing this, if the same configuration of owing/owed people can occur via different paths, we compute it only once. This turns the exponential search into something more manageable because the number of distinct states is limited. With up to 12 people, the total number of subsets of people is 2^{12} = 4096 at most. Exploring all subsets (with some additional factor for checking sums or pairing) is feasible.

Summary of Optimizations:

• Use bitmask DP to systematically consider groups of people that can settle among themselves.
• Use memoization in recursive/backtracking solutions to avoid duplicate work.
• Leverage the small input size to try these exponential techniques, which would not work for large n but are fine here.
• These optimizations ensure we don’t explore the same state more than once, dramatically reducing the search space from pure brute force.

Step-by-Step Walkthrough with Visual Examples

Let’s walk through a concrete example to see how the algorithm works step by step. We’ll use Example 1 for a detailed walkthrough:

Example 1 Revisited: transactions = [[0,1,10], [2,0,5]] (Person 0 paid $10 to Person 1, and Person 2 paid $5 to Person 0).

• Step 1: Calculate net balances.
  Start with all balances = 0.
  Transaction [0,1,10]: Person 0 gave out $10, Person 1 received $10.
  – Update balance[0] = -10 (owes $10), balance[1] = +10 (is owed $10).
  Transaction [2,0,5]: Person 2 gave out $5, Person 0 received $5.
  – Update balance[2] = -5 (owes $5), balance[0] = -10 + 5 = -5 (now owes $5 after receiving $5).
  Resulting net balances:
  Person 0: -5 (meaning overall person 0 paid $5 more than they received, so others owe 0 $5)
  Person 1: +10 (person 1 received $10 more than paid, so they owe $10 out to others)
  Person 2: -5 (person 2 paid $5 more than received, so others owe 2 $5)

• Step 2: Filter out zero balances.
  In this example, no balance is zero (all three people have non-zero balances). If someone had a zero balance, we would exclude them from further steps.

• Step 3: Identify debtors and creditors.
  Debtors (negative balances): Person 0 (-5), Person 2 (-5). They should receive money in the settling transactions.
  Creditors (positive balances): Person 1 (+10). This person needs to pay out money in settling transactions.
  Essentially, person 1 owes $10 in total, and persons 0 and 2 are together owed $10 (5 each).

• Step 4: Settle one person’s balance at a time (Backtracking).
  We take the first person with a non-zero balance – Person 0 (balance -5). Person 0 is a debtor (needs $5). We look for a creditor to give money to Person 0. The only creditor here is Person 1 (balance +10).

  – Have Person 1 pay Person 0 $5. This is one transaction. After this transaction, update their balances: Person 0’s balance becomes -5 + 5 = 0 (debt settled!), Person 1’s balance becomes +10 - 5 = +5 (person 1 still has $5 to give to others). Person 2 remains -5.
  – We have reduced the problem: now Person 0 is settled. The remaining unsettled balances are Person 1: +5, Person 2: -5.

• Step 5: Continue to next unsettled person.
  Now skip Person 0 (it’s zero). Next is Person 1 with +5. Person 1 is a creditor (is owed nothing now, rather owes others $5 because +5 means they have extra $5 that must go to someone). Person 1 can settle with Person 2 who has -5.
  – Have Person 1 pay Person 2 $5. This is a second transaction. After this, Person 1’s balance +5 - 5 = 0, Person 2’s balance -5 + 5 = 0.
  – Now all persons 0, 1, and 2 are settled (balance 0 for everyone).

• Step 6: End recursion.
  We have no more unsettled balances. We used 2 transactions in total, which matches the output. The sequence of transactions we performed is: (1 pays 0 $5) and (1 pays 2 $5). This is indeed the optimal minimum.

Throughout this process, we made choices that led to the optimal outcome:

• We always settled one person completely before moving on (which ensures progress and limits the recursion depth).
• We chose transactions that eliminate a debt entirely (each transaction set one person’s balance to zero).
• If there were multiple options, we would explore them and find the minimum. For instance, in this example Person 1 had to pay both Person 0 and Person 2 anyway, but if there was a choice of whom to pay first, both orders yield 2 total transactions. The algorithm would consider both, but it would realize all lead to 2 in the end.

Visualizing Example 1: Imagine Person 1 has $10 that needs to go to Person 0 and Person 2 (who are each owed $5). Person 1 basically splits that $10 and gives it to 0 and 2. That’s why 2 transactions are needed – one to each of the other people. There’s no way to do it in 1 transaction because one transaction can only involve two people (one payer and one receiver) at a time, so Person 1 can’t pay $5 to two people in a single transaction.

Example 2 Revisited (Briefly): transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]. We saw that the answer is 1. Let’s verify quickly:

• Compute net balances:
  • Person 0: paid 10 to 1, received 1 from 1 and 5 from 2. Net = -10 + 1 + 5 = -4.
  • Person 1: received 10 from 0, paid 1 to 0 and 5 to 2. Net = +10 - 1 - 5 = +4.
  • Person 2: received 5 from 1, paid 5 to 0. Net = +5 - 5 = 0.
• Filter zeros: Person 2 has net 0, ignore Person 2.
• We have Person 0 with -4 and Person 1 with +4. They owe each other exactly $4 (in opposite directions of debt). So one transaction can settle this: Person 1 pays Person 0 $4. After that, Person 0’s balance becomes 0 and Person 1’s becomes 0. Done in 1 transaction. This matches the explanation that “person #1 only need to give person #0 $4, and all debt is settled.”

The step-by-step approach we demonstrated can be applied to any set of balances. The backtracking algorithm ensures all possibilities are checked, but intelligently, so we find the absolute minimum number of transactions required.

Code Implementations

Below are implementations of the solution in both Python and Java. Both approaches use the backtracking strategy described above to find the minimum number of settling transactions.

Python Solution