DSA problem
Optimal Account Balancing
You are given an array transactions where transactions[i] = [from, to, amount] indicates that person from gave amount to person to. Compute the minimum number of additional transactions needed to settle all debts so that every person's net balance is zero.
The first reduction: only net balances matter. Sum up each person's receipts minus payments. People with a balance of 0 can be discarded. Let debts be the array of remaining non-zero balances. We must group these balances so that each group sums to zero, and within a group of size g exactly g - 1 transactions suffice (a star configuration). So the answer is n - (number of zero-sum groups), where n = len(debts). Equivalently, minimize transactions = maximize the count of zero-sum subsets in a partition.
This is NP-hard in general, but n <= 12 makes a subset DP tractable. Let maxSubsets[mask] = the maximum number of zero-sum subsets you can partition the chosen subset mask into. Recurrence: maxSubsets[mask] = max over submasks s of mask with sum(s) == 0 of maxSubsets[mask ^ s] + 1. Base case maxSubsets[0] = 0. Final answer = n - maxSubsets[(1 << n) - 1].
To enumerate submasks of mask efficiently use for s = mask; s > 0; s = (s - 1) & mask. Precompute sums[mask] for every subset (the total balance of those people). Total complexity is O(3^n) for the submask enumeration plus O(2^n * n) for the sum precomputation — easy for n <= 12.
Examples
transactions = [[0,1,10],[2,0,5]]2transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]1transactions = [[0,1,5]]1Constraints
- 1 <= transactions.length <= 8
- transactions[i].length == 3
- 0 <= from, to < 12
- from != to
- 1 <= amount <= 100
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.