465. Optimal Account Balancing

first, found the len is so samll, so it must a dfs backtracking problem

T: O(n!), not sure, n is transactions array size

S: O(n)

class Solution {
    public int minTransfers(int[][] transactions) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] t : transactions) {
            map.put(t[0], map.getOrDefault(t[0], 0) - t[2]);
            map.put(t[1], map.getOrDefault(t[1], 0) + t[2]);
        }
        
        return dfs(0, new ArrayList<>(map.values()));
    }
    private int dfs(int start, List<Integer> debt) {
        int n = debt.size();
        
        while (start < n && debt.get(start) == 0) {
            start++;
        }
        if (start == n) {
            return 0;
        }
        Integer res = Integer.MAX_VALUE;
        
        // 固定一個數(start), 對其他的數(for start+1 to n)做窮舉, 所以呼叫 dfs 要到下層是 start + 1 
        int prev = debt.get(start);
        for (int i = start+1; i < n; i++) {
            int cur = debt.get(i);
            if (prev * cur < 0) { // 一正一負時才 try dfs
                debt.set(i, cur + prev);
                res = Math.min(res, 1 + dfs(start+1, debt)); // count+1
                debt.set(i, cur); // 因為是 set, 所以不用 - prev (也可以 debt.get(i) - prev), 但反正有原始值
                
                if (prev + cur == 0) { // pruning, 已經平衡了, 就不用繼續 try
                    break;
                }
            }
        }
        return res;
    }
}

/*
minimum number of transactions required to settle the debt

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

  5   10
2-> 0 -> 1

1 give 0 5
1 give 2 5

1 -10
0. 5
2. 5

*/

global variable version

class Solution {
    int res = Integer.MAX_VALUE;
    public int minTransfers(int[][] transactions) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] t : transactions) {
            map.put(t[0], map.getOrDefault(t[0], 0) - t[2]);
            map.put(t[1], map.getOrDefault(t[1], 0) + t[2]);
        }
        dfs(0, new ArrayList<>(map.values()), 0);
        return res;
    }
    private void dfs(int start, List<Integer> debt, int count) {
        int n = debt.size();
        
        while (start < n && debt.get(start) == 0) {
            start++;
        }
        if (start == n) {
            res = Math.min(res, count);
            return;
        }
        
        // 固定一個數(start), 對其他的數(for start+1 to n)做窮舉, 所以呼叫 dfs 要到下層是 start + 1 
        int prev = debt.get(start);
        for (int i = start+1; i < n; i++) {
            int cur = debt.get(i);
            if (prev * cur < 0) { // 一正一負時才 try dfs
                debt.set(i, cur + prev);
                dfs(start+1, debt, count+1); // count+1
                debt.set(i, cur); // 因為是 set, 所以不用 - prev (也可以 debt.get(i) - prev), 但反正有原始值
                
                if (prev + cur == 0) { // pruning, 已經平衡了, 就不用繼續 try
                    break;
                }
            }
        }
    }
}