Optimal Account Balancing

hard backtracking bitmask dp

Problem

Given a list of transactions [from, to, amount], return the minimum number of payments required to settle every balance to zero.

Inputtransactions = [[0,1,10],[2,0,5]]

Output2

Balances: 0:-5, 1:10, 2:-5 → two payments suffice.

transactions (from,to,amt ;)

def min_transfers(transactions):
    bal = {}
    for a, b, v in transactions:
        bal[a] = bal.get(a, 0) - v
        bal[b] = bal.get(b, 0) + v
    debts = [v for v in bal.values() if v]
    def back(i):
        while i < len(debts) and debts[i] == 0: i += 1
        if i == len(debts): return 0
        best = float("inf")
        for j in range(i + 1, len(debts)):
            if debts[j] * debts[i] < 0:
                debts[j] += debts[i]
                best = min(best, 1 + back(i + 1))
                debts[j] -= debts[i]
        return best
    return back(0)

function minTransfers(transactions) {
  const bal = new Map();
  for (const [a, b, v] of transactions) {
    bal.set(a, (bal.get(a) || 0) - v);
    bal.set(b, (bal.get(b) || 0) + v);
  }
  const debts = [...bal.values()].filter(v => v);
  function back(i) {
    while (i < debts.length && debts[i] === 0) i++;
    if (i === debts.length) return 0;
    let best = Infinity;
    for (let j = i + 1; j < debts.length; j++) {
      if (debts[j] * debts[i] < 0) {
        debts[j] += debts[i];
        best = Math.min(best, 1 + back(i + 1));
        debts[j] -= debts[i];
      }
    }
    return best;
  }
  return back(0);
}

class Solution {
    List debts;
    public int minTransfers(int[][] transactions) {
        Map bal = new HashMap<>();
        for (int[] t : transactions) {
            bal.merge(t[0], -t[2], Integer::sum);
            bal.merge(t[1], t[2], Integer::sum);
        }
        debts = new ArrayList<>();
        for (int v : bal.values()) if (v != 0) debts.add(v);
        return back(0);
    }
    int back(int i) {
        while (i < debts.size() && debts.get(i) == 0) i++;
        if (i == debts.size()) return 0;
        int best = Integer.MAX_VALUE;
        for (int j = i + 1; j < debts.size(); j++) {
            if ((long) debts.get(j) * debts.get(i) < 0) {
                debts.set(j, debts.get(j) + debts.get(i));
                best = Math.min(best, 1 + back(i + 1));
                debts.set(j, debts.get(j) - debts.get(i));
            }
        }
        return best;
    }
}

class Solution {
    vector debts;
    int back(int i) {
        while (i < (int)debts.size() && debts[i] == 0) i++;
        if (i == (int)debts.size()) return 0;
        int best = INT_MAX;
        for (int j = i + 1; j < (int)debts.size(); j++) {
            if ((long long) debts[j] * debts[i] < 0) {
                debts[j] += debts[i];
                best = min(best, 1 + back(i + 1));
                debts[j] -= debts[i];
            }
        }
        return best;
    }
public:
    int minTransfers(vector>& transactions) {
        unordered_map bal;
        for (auto& t : transactions) { bal[t[0]] -= t[2]; bal[t[1]] += t[2]; }
        for (auto& [_, v] : bal) if (v != 0) debts.push_back(v);
        return back(0);
    }
};

Explanation

Who paid whom doesn't matter for the final count — only each person's net balance does. So we first collapse all transactions into a balance per person (money owed is negative, money to receive is positive) and throw away anyone at zero.

Now the task is: settle these signed debts with the fewest payments. We use backtracking. The function back(i) settles the first person who still has a non-zero balance, debts[i], by pairing them with someone who has the opposite sign.

For each later person j where debts[j] * debts[i] < 0 (opposite signs), we transfer debts[i] into debts[j], which zeroes out person i in one payment. We recurse with 1 + back(i + 1), then undo the transfer to try other pairings, keeping the minimum.

Example: balances 0:-5, 1:+10, 2:-5. Person 0 pays into person 1, and person 2 pays into person 1 — two payments clear everyone, so the answer is 2.

Trying every valid opposite-sign partner and taking the best guarantees the true minimum number of transfers.

Time: O(n!) Space: O(n)