AlgoMaster Logo

Optimal Account Balancing

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We have a group of people who owe each other money through various transactions. Our job is to figure out the fewest number of new transactions needed so that everyone's debts are fully settled.

Who paid whom originally does not matter. All that matters is each person's net balance, the total amount they received minus the total amount they paid. A person with a positive balance is a creditor (others owe them money). A person with a negative balance is a debtor (they owe money to others). A person with a zero balance is already settled and can be ignored.

Once we have the net balances, the problem becomes: given a set of positive and negative numbers that sum to zero, find the minimum number of transfers to make all balances zero. Finding this minimum is NP-hard in general, which is why the constraints are small (at most 8 transactions, at most 12 people).

Key Constraints:

  • 1 <= transactions.length <= 8 → Very few transactions, so very few people are involved. This small bound allows exponential approaches like backtracking or bitmask DP.
  • 0 <= from_i, to_i < 12 → At most 12 distinct people, and many may net out to zero. Only the non-zero balances feed into the search, so the working set size n is at most 12.
  • 1 <= amount_i <= 100 → Amounts are integers, so balances are integers and there is no floating-point rounding to worry about.

Approach 1: Backtracking (Try All Pairings)

Intuition

Compute each person's net balance, then try every way to pair debtors with creditors, transferring money between them until all balances reach zero. Track the number of transactions used and return the minimum across all possibilities.

The search stays manageable by processing people in a fixed order. Take the first person with a non-zero balance and settle their entire balance against one later person who has an opposite sign. The transfer adds person start's full balance to person j, treating person start as resolved. The recursion then advances to start + 1 and never reads balances[start] again, so person start is effectively settled.

Settling person start completely in one transfer is safe to assume. Person start's balance has to be cleared by some transactions eventually, and any optimal settlement can be reordered so that the transactions touching start come first and combine into a single transfer of the full amount onto one other party. Fixing the order this way avoids exploring permutations that settle the same set of people in a different sequence.

Algorithm

  1. Compute the net balance for each person using a hash map. For each transaction [from, to, amount], subtract amount from from's balance and add amount to to's balance.
  2. Collect all non-zero balances into a list.
  3. Define a recursive function backtrack(start) that:
    • Skips over any indices at start or beyond that already have zero balance.
    • If start reaches the end of the list, return 0 (all settled).
    • For each index j from start + 1 to end, if balances[j] has the opposite sign of balances[start], transfer balances[start] to person j (add balances[start] to balances[j]), recurse with backtrack(start + 1), then undo the transfer.
    • Return 1 + the minimum result across all valid j choices.
  4. Return the result of backtrack(0).

Example Walkthrough

1Net balances computed: Person 0=-5, Person 1=+10, Person 2=-5
0
-5
start
1
10
2
-5
1/6

Code

This backtracking explores many redundant branches. A small pruning rule cuts most of them without changing the answer.

Approach 2: Backtracking with Greedy Pruning

Intuition

One pruning rule cuts most of the redundant branches. When a transfer brings person j to exactly zero, both person start and person j are fully settled by that single transaction. When such an exact match exists, the search can take it and stop trying other partners for person start.

This is safe because an exact match settles two people for the price of one transaction, while any other partner leaves person j non-zero and still requires at least one more transaction to clear later. No alternative for this step can use fewer transactions, so there is no reason to explore them. The worst-case complexity is unchanged, but on these inputs the pruned search finishes far sooner.

Algorithm

  1. Compute net balances the same way as Approach 1.
  2. In the recursive function, when a transfer makes balances[j] become zero (both people fully settled), take that result immediately without exploring further options for this step.
  3. Otherwise, continue exploring all valid opposite-sign pairings and return the minimum.

Example Walkthrough

1Net balances: [-9, 5, 2, 2] (Person 3 had 0, removed)
0
-9
start
1
5
2
2
3
2
1/7

Code

Both backtracking versions settle people one transfer at a time and never recognize that groups of people can settle among themselves. Reframing the problem around independent zero-sum groups leads to a faster solution with a worst-case bound that beats factorial.

Approach 3: Bitmask DP (Optimal)

Intuition

With n people who have non-zero balances, the minimum number of transactions is n - k, where k is the maximum number of disjoint groups whose balances each sum to zero. A group of m people whose balances sum to zero settles with exactly m - 1 transactions: line them up, have person 1 pass their balance to person 2, person 2 pass the running total to person 3, and so on, until the last person receives exactly what they are owed. So partitioning n people into k zero-sum groups costs (m1 - 1) + ... + (mk - 1) = n - k transactions, and minimizing transactions means maximizing the number of groups k.

The problem reduces to partitioning the balances into as many zero-sum subsets as possible. A bitmask over the n people represents each subset, and a DP over masks finds the partition with the most zero-sum groups.

Algorithm

  1. Compute net balances and collect non-zero ones into an array of size n.
  2. Precompute subsetSum[mask] for all 2^n subsets using bitmask iteration.
  3. Create a DP array where dp[mask] = maximum number of zero-sum subsets that the people in mask can be partitioned into.
  4. For each mask from 1 to 2^n - 1:
    • For each submask of mask (iterate submasks using sub = (sub - 1) & mask):
      • If subsetSum[sub] == 0, then dp[mask] = max(dp[mask], dp[mask ^ sub] + 1).
  5. The answer is n - dp[(1 << n) - 1].

Example Walkthrough

1Net balances: [-5, 10, -5], n=3. Goal: max zero-sum groups.
0
-5
1
10
2
-5
1/5

Code