465. DFS backtracking of optimal bill balance

 465. Optimal bill balance

A group of friends will borrow money from each other during their holidays . for instance , Xiao AI paid Xiao Xin's lunch for a total of 10 dollar . If Xiao Ming pays Xiao AI's taxi money, the total amount is 5 dollar . We can use a triple (x, y, z) Indicates a transaction , Express x lend y total z dollar . use 0, 1, 2 I love my classmates 、 Xiao Xin and Xiao Ming （0, 1, 2 Human label ）, The above transaction can be expressed as  [[0, 1, 10], [2, 0, 5]].

Given a list of transaction information between a group of people , Calculate the minimum number of times you can pay off all your debts .

Be careful ：

1. A trade fair is represented by triples (x, y, z) Express , And there are  x ≠ y  And  z > 0.
2. People's labels may not be in order , For example, the label may be 0, 1, 2 Also may be 0, 2, 6.

Example 1：

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

 Output ：
2

 explain ：
 people  #0  Give a person  #1  total  10  dollar .
 people  #2  Give a person  #0  total  5  dollar .

 Need two transactions . One way is people  #1  Give people separately  #0  And people  #2  various  5  dollar .

Example 2：

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

 Output ：
1

 explain ：
 people  #0  Give a person  #1  total  10  dollar .Person #0 gave person #1 $10.
 people  #1  Give a person  #0  total  1  dollar .Person #1 gave person #0 $1.
 people  #1  Give a person  #2  total  5  dollar .Person #1 gave person #2 $5.
 people  #2  Give a person  #0  total  5  dollar .Person #2 gave person #0 $5.

 therefore , people  #1  Need to give people  #0  total  4  dollar , All debts can be paid off .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/optimal-account-balancing
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The result of doing the question

success （ Almost failed . Encountered two wrong ideas , The first mistake was to write greedy and change it twice , Then I realized that greedy error is polynomial ; The second is enumeration, which only enumerates one side , Because the length of positive and negative sets is different , So both sides should be used , Enumeration is required , Learned here , Only those with equal length matching can be enumerated on one side , Otherwise, enumerate on both sides ）

Method ：DFS

1. Calculate the amount of each person (x,y,z) , x many 10 element , y Less 10 element 【 And vice versa , Ensure the same direction of calculation 】
2. 0 The balance of yuan is ignored , The rest , Positive numbers are grouped , Negative numbers are grouped
3. DFS Enumerate all the situations ：
   • The balance is 0： Both positive and negative amounts consume one
   • Negative balance , Positive numbers consume one
   • The balance is positive , Negative numbers consume one
   • The balance is 0, And the positive and negative sets have been cycled to the end , end , Compare the smallest answer

class Solution {
        public int minTransfers(int[][] transactions) {
            Map<Integer,Integer> map = new HashMap<>();
            for(int[] transaction:transactions){
                int a = transaction[0];
                int b = transaction[1];
                int c = transaction[2];
                map.put(a,map.getOrDefault(a,0)+c);
                map.put(b,map.getOrDefault(b,0)-c);
            }

            List<Integer> a = new ArrayList<>();
            List<Integer> b = new ArrayList<>();
            for(int money:map.values()){
                if(money>0) a.add(money);
                if(money<0) b.add(money);
            }
            dfs(a,b,0,0,0,0);
            return ans;
        }

        int ans = Integer.MAX_VALUE;

        private void dfs(List<Integer> a, List<Integer> b, int last, int ia, int ib,int time){
            if(ia == a.size() && ib == b.size()){
                ans = Math.min(time,ans);
                return;
            }

            if(last>0){
                for(int i = ib; i < b.size(); i++){
                    swap(b,ib,i);
                    dfs(a,b,last+b.get(ib),ia,ib+1,time+1);
                    swap(b,ib,i);
                }

                return;
            }

            for(int i = ia; i < a.size(); i++){
                swap(a,ia,i);
                if(last == 0){
                    dfs(a,b,last+a.get(ia)+b.get(ib),ia+1,ib+1,time+1);
                }else{
                    dfs(a,b,last+a.get(ia),ia+1,ib,time+1);
                }
                swap(a,ia,i);
            }
        }

        private void swap(List<Integer> a, int x, int y){
            int temp = a.get(x);
            a.set(x,a.get(y));
            a.set(y,temp);
        }
    }