13ms backtracking Java solution with optimization


  • 1
    B

    Since this problem is NPC problem, my original backtracking solution always gets a TLE, but we know the upper bound of this problem is the number of the transactions, it can not exceed this number since we can always return the money back from this person to that person.
    Therefore, we can see many parts in the code will not need to be done. Alos we should know that the size of my list will be the lower bound of my transaction for the solution. The number of transactions have been done plus the size of our lists should not be larger than that upper bound. By using this optimization, I can get AC.

    Here is the code:

    '''
    public class Solution {
    int res = 0;
    public int minTransfers(int[][] transactions) {
    HashMap<Integer, Integer> map = new HashMap<>();

        res = transactions.length;
        for (int[] i : transactions) {
            if (!map.containsKey(i[0])) map.put(i[0], 0);
            if (!map.containsKey(i[1])) map.put(i[1], 0);
            map.put(i[0], map.get(i[0]) - i[2]);
            map.put(i[1], map.get(i[1]) + i[2]);
        }
        
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        
        for (int i : map.values()) {
            if (i > 0) list1.add(i);
            else if (i < 0) list2.add(-i);
        }
        
        
        backtrack(list1, list2, 0);
        
        return res;
    }
    
    private void backtrack(List<Integer> list1, List<Integer> list2, int p) {
        if (p >= res) return;
        if (list1.isEmpty()) {
            res = Math.min(p, res);
            return;
        }
        int n1 = list1.size();
        int n2 = list2.size();
        if (p + n1 >= res || p + n2 >= res) return; //key optimization part
        for (int i = 0; i < n1; i++) {
            int v1 = list1.remove(i);
            for (int j = 0; j < n2; j++) {
                int v2 = list2.remove(j);
                if (v1 > v2) {
                    list1.add(v1 - v2);
                    backtrack(list1, list2, p + 1);
                    list1.remove(list1.size() - 1);
                }
                else if (v1 < v2) {
                    list2.add(v2 - v1);
                    backtrack(list1, list2, p + 1);
                    list2.remove(list2.size() - 1);
                }
                else backtrack(list1, list2, p + 1);
                list2.add(j, v2);
            }
            list1.add(i, v1);
        }
    
        return;
    }
    

    }
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.