Why is my java solution TLE?


  • 1
    D

    I learned from discussion that this problem can be solved by a method from 0/1 knapsack problem. I use map<int, map> to simulate a 2D array, and I used a recursive style of method to accelerate the algorithm (hopefully). But why does it cause TLE?

    public class Solution {
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length <= 1) {
                return false;
            }
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % 2 == 1) {
                return false;
            }
            int n = nums.length;
            Map<Integer, Map<Integer, Boolean>> dp = new HashMap<>();
            return calc(nums, n, dp, n - 1, sum / 2);
        }
    
        private boolean calc(int[] nums, int n, Map<Integer, Map<Integer, Boolean>> dp, int i, int j) {
            if (contains(dp, i, j)) {
                return get(dp, i, j);
            }
            if (j < 0) {
                return false;
            }
            if (i == 0) {
                if (nums[i] == j) {
                    put(dp, i, j, true);
                    return true;
                } else {
                    put(dp, i, j, false);
                    return false;
                }
            }
            put(dp, i, j, calc(nums, n, dp, i - 1, j) || calc(nums, n, dp, i - 1, j - nums[i]));
            return get(dp, i, j);
        }
    
        private boolean contains(Map<Integer, Map<Integer, Boolean>> dp, int i, int j) {
            return dp.containsKey(i) && dp.get(i).containsKey(j);
        }
    
        private void put(Map<Integer, Map<Integer, Boolean>> dp, int i, int j, boolean b) {
            if (!dp.containsKey(i)) {
                dp.put(i, new HashMap<Integer, Boolean>());
            }
            dp.get(i).put(j, b);
        }
    
        private boolean get(Map<Integer, Map<Integer, Boolean>> dp, int i, int j) {
            return contains(dp, i, j) ? dp.get(i).get(j) : false;
        }
    }
    

  • 0
    C

    @dachuan.huang said in Why is my java solution TLE?:

    put(dp, i, j, calc(nums, n, dp, i - 1, j) || calc(nums, n, dp, i - 1, j - nums[i]));

    I changed this line, now your code runs 43ms and gets accepted.

    put(dp, i, j, calc(nums, n, dp, i - 1, j - nums[i]) || calc(nums, n, dp, i - 1, j));   // put better chance of True ahead
    

    I also tried to do some minor improvement as below, it now runs 18ms.

        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length <= 1) {
                return false;
            }
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % 2 == 1) {
                return false;
            }        
            Map<Integer, Map<Integer, Boolean>> dp = new HashMap<>();
            return calc(nums, dp, nums.length - 1, sum / 2);
        }
        
        private boolean calc(int[] nums, Map<Integer, Map<Integer, Boolean>> dp, int i, int j) {
            if (contains(dp, i, j)) {
                return get(dp, i, j);
            }        
            if(j == 0) {
                put(dp, i, j, true);
                return true;
            }
            if (i == -1 || j < 0) {            
                put(dp, i, j, false);
                return false;            
            }        
            put(dp, i, j, calc(nums, dp, i - 1, j - nums[i]) || calc(nums, dp, i - 1, j));
            return get(dp, i, j);
        }
         
        private boolean contains(Map<Integer, Map<Integer, Boolean>> dp, int i, int j) {
            return dp.containsKey(i) && dp.get(i).containsKey(j);
        }
    
        private void put(Map<Integer, Map<Integer, Boolean>> dp, int i, int j, boolean b) {
            if (!dp.containsKey(i)) {
                dp.put(i, new HashMap<Integer, Boolean>());
            }
            dp.get(i).put(j, b);
        }
    
        private boolean get(Map<Integer, Map<Integer, Boolean>> dp, int i, int j) {        
            return dp.get(i).get(j);
        }
    

Log in to reply
 

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