465. Optimal Account Balancing

You are given an array of transactions transactions where transactions[i] = [fromi, toi, amounti] indicates that the person with ID = fromi gave amounti $ to the person with ID = toi.

Return the minimum number of transactions required to settle the debt.

Example 1:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

Example 2:

Input: transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Output: 1
Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.
Therefore, person #1 only need to give person #0 $4, and all debt is settled.

Constraints:

• 1 <= transactions.length <= 8

• transactions[i].length == 3

• 0 <= fromi, toi <= 20

• fromi != toi

• 1 <= amounti <= 100

Solution

To find the minimum transaction times, we first want to know their asset status. (How much money do they have in hand? and How much money they owed others?) With that information, we can know if asset[i] > 0, Person i has money (ie, he owed someone money) asset[i] < 0, Person i is the creditor. Some people owned him money.

To settle the debt, our goal is to make the asset[i] = 0, for all i.

We find the problem's sub-problem is also similar to the original problem but with a smaller scale. Perhaps it is a good idea to try DP or backtracking. To reduce the scope of the problem, there are several choices for i, which asset[i] != 0. He can give all his money or debt to another person j who's sign of asset[j] is opposite to asset[i], so that asset[i] == 0. However, we don't have a clear idea to decide which way will lead to the minimum transaction times.

So we decide to use backtracking

    public int minTransfers(int[][] transactions) {
        Map<Integer, Integer> assets = new HashMap<>();
        for(int[] trans : transactions) {
            assets.put(trans[0], assets.getOrDefault(trans[0], 0) - trans[2]);
            assets.put(trans[1], assets.getOrDefault(trans[1], 0) + trans[2]);
        }
        return helper(new ArrayList<>(assets.values()), 0);
    }
    
    public int helper(List<Integer> assets, int start){
        while(start < assets.size() && assets.get(start) == 0) {
            start++;
        }
        if(start == assets.size()) return 0;
        int prev = assets.get(start);
        int r = Integer.MAX_VALUE;
        for(int i = start + 1; i < assets.size(); i++) {
            if(prev * assets.get(i) < 0) {
                assets.set(start, 0);
                assets.set(i, assets.get(i) + prev);
                r = Math.min(r, 1 + helper(assets, start+1));
                assets.set(start, prev);
                assets.set(i, assets.get(i) - prev);
            }
        }
        return r;
    }