Optimal Account Balancing

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

func minTransfers(transactions [][]int) int {
    bal := make(map[int]int64)
    for _, t := range transactions {
        bal[t[0]] -= int64(t[2])
        bal[t[1]] += int64(t[2])
    }
    var nz []int64
    for _, v := range bal {
        if v != 0 {
            nz = append(nz, v)
        }
    }
    var dfs func(start int) int
    dfs = func(start int) int {
        for start < len(nz) && nz[start] == 0 {
            start++
        }
        if start == len(nz) {
            return 0
        }
        best := math.MaxInt32
        for j := start + 1; j < len(nz); j++ {
            if nz[j]*nz[start] < 0 {
                nz[j] += nz[start]
                if cand := 1 + dfs(start+1); cand < best {
                    best = cand
                }
                nz[j] -= nz[start]
            }
        }
        return best
    }
    return dfs(0)
}

from collections import defaultdict
from typing import List

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        bal: dict[int, int] = defaultdict(int)
        for f, t, a in transactions:
            bal[f] -= a
            bal[t] += a
        nz = [v for v in bal.values() if v != 0]

        def dfs(start: int) -> int:
            while start < len(nz) and nz[start] == 0:
                start += 1
            if start == len(nz):
                return 0
            best = float('inf')
            for j in range(start + 1, len(nz)):
                if nz[j] * nz[start] < 0:
                    nz[j] += nz[start]
                    best = min(best, 1 + dfs(start + 1))
                    nz[j] -= nz[start]
            return best

        return dfs(0)

function minTransfers(transactions) {
    const bal = new Map();
    for (const [f, t, a] of transactions) {
        bal.set(f, (bal.get(f) ?? 0) - a);
        bal.set(t, (bal.get(t) ?? 0) + a);
    }
    const nz = [];
    for (const v of bal.values()) {
        if (v !== 0) nz.push(v);
    }
    const dfs = (start) => {
        while (start < nz.length && nz[start] === 0) start++;
        if (start === nz.length) return 0;
        let best = Infinity;
        for (let j = start + 1; j < nz.length; j++) {
            if (nz[j] * nz[start] < 0) {
                nz[j] += nz[start];
                best = Math.min(best, 1 + dfs(start + 1));
                nz[j] -= nz[start];
            }
        }
        return best;
    };
    return dfs(0);
}

class Solution {
    private long[] nz;

    public int minTransfers(int[][] transactions) {
        Map<Integer, Long> bal = new HashMap<>();
        for (int[] t : transactions) {
            bal.merge(t[0], -(long) t[2], Long::sum);
            bal.merge(t[1], (long) t[2], Long::sum);
        }
        List<Long> list = new ArrayList<>();
        for (long v : bal.values()) {
            if (v != 0) list.add(v);
        }
        nz = new long[list.size()];
        for (int i = 0; i < list.size(); i++) nz[i] = list.get(i);
        return dfs(0);
    }

    private int dfs(int start) {
        while (start < nz.length && nz[start] == 0) start++;
        if (start == nz.length) return 0;
        int best = Integer.MAX_VALUE;
        for (int j = start + 1; j < nz.length; j++) {
            if (nz[j] * nz[start] < 0) {
                nz[j] += nz[start];
                int cand = 1 + dfs(start + 1);
                if (cand < best) best = cand;
                nz[j] -= nz[start];
            }
        }
        return best;
    }
}

function minTransfers(transactions: number[][]): number {
    const bal = new Map<number, number>();
    for (const [f, t, a] of transactions) {
        bal.set(f, (bal.get(f) ?? 0) - a);
        bal.set(t, (bal.get(t) ?? 0) + a);
    }
    const nz: number[] = [];
    for (const v of bal.values()) {
        if (v !== 0) nz.push(v);
    }
    const dfs = (start: number): number => {
        while (start < nz.length && nz[start] === 0) start++;
        if (start === nz.length) return 0;
        let best = Infinity;
        for (let j = start + 1; j < nz.length; j++) {
            if (nz[j] * nz[start] < 0) {
                nz[j] += nz[start];
                best = Math.min(best, 1 + dfs(start + 1));
                nz[j] -= nz[start];
            }
        }
        return best;
    };
    return dfs(0);
}