leetcode465

Optimal Account Balancing, hard
Settling Multiple Debts Efficiently: An Invitation to Computing Science by T. Verhoeff, June 2003. http://www.mathmeth.com/tom/files/settling-debts.pdf
The question can be transferred to a 3-partition problem, which is NP-Complete.

recursion + backtracking, get the total transaction and then dfs and backtracing every trans.
Core code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int backtrack(Long[] debts, int pos, int count){
        while(pos < debts.length && debts[pos] == 0) pos++;
        if (pos >= debts.length) {
            return count;
        }
        int res = Integer.MAX_VALUE;
        for(int i = pos + 1; i < debts.length; i++){
            if(debts[pos] * debts[i] < 0){
              debts[i] += debts[pos];
              res = Math.min(res, helper(debts, pos + 1, count + 1));
              debts[i] = debts[i] - debts[pos];
            }
        }
        return res;
    }