Java: boolean matrix time limit exceeds but boolean object matrix works fine
nixamani5
24

This is for 416. Partition Equal Subset Sum:

why does this boolean matrix gives time limit exceeded
#solution 1

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if(sum % 2 == 1){
            return false;
        }
        sum = sum / 2;
        int n = nums.length;        
        boolean memo [][] = new boolean[n + 1][sum + 1];
       return knapsack(nums, sum, n, memo);
    }
    
    boolean knapsack(int nums[], int sum, int n, boolean memo[][]){
        if(sum == 0){
            return true;
        } 
        if(n == 0){
            return false;
        }
        
        if(memo[n][sum] == true){
            return memo[n][sum];
        }
        
        if(nums[n - 1] > sum){
            memo[n][sum] = knapsack(nums, sum, n - 1, memo);
        }
        else{
           memo[n][sum] =  knapsack(nums, sum - nums[n - 1] , n - 1, memo) || knapsack(nums, sum, n - 1, memo);
        }
        
        return memo[n][sum];
    }
	}

how ever instead of boolean[][] Boolean[][] works fine
#solution 2

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if(sum % 2 == 1){
            return false;
        }
        sum = sum / 2;
        int n = nums.length;        
        Boolean memo [][] = new Boolean[n + 1][sum + 1];
       return knapsack(nums, sum, n, memo);
    }
    
    boolean knapsack(int nums[], int sum, int n, Boolean memo[][]){
        if(sum == 0){
            return true;
        } 
        if(n == 0){
            return false;
        }
        
        if(memo[n][sum] != null){
            return memo[n][sum];
        }
        
        if(nums[n - 1] > sum){
            memo[n][sum] = knapsack(nums, sum, n - 1, memo);
        }
        else{
           memo[n][sum] =  knapsack(nums, sum - nums[n - 1] , n - 1, memo) || knapsack(nums, sum, n - 1, memo);
        }
        
        return memo[n][sum];
    }
	}

Could anyone address this? this seems very strange to me.

Comments (0)