Leetcode 416

Using memoization
class Solution {
    public boolean canPartition(int[] nums) {
        
        Arrays.sort(nums);
        int total = 0;
        
        for(int num:nums)
        total+=num;
        
        
        if(total%2!=0)
        return false;
        
        return canPartition(nums,0,0,total, new HashMap<String, Boolean>());
        
    }
    
    public boolean canPartition(int[] nums, int index,  int sum , int total , HashMap<String,Boolean> state)
    {
        String current = index + "" + sum;
        
        if(state.containsKey(current))
            return state.get(current);
        
        if(sum*2==total)
            return true;
        
        if(sum > total || index >= nums.length)
            return false;
        
        boolean result =  canPartition(nums, index+1 , sum , total,state) ||  canPartition(nums,index+1,sum+nums[index],total,state );
        
        state.put(current, result);
        
        return result;
        
    }
    
}

Similar codes

0 vote154 views1 answer
What Is Spring Boot and What Are Its Main Features?
Java Spring
0 vote130 views1 answer
Java all alphabet characters
Java
0 vote142 views1 answer
Error creating bean with name 'org.springframework.cloud.netflix.eureka.server.EurekaServerInitializerConfiguration'
Java
0 vote139 views1 answer
Java project with submodules
Java
0 vote143 views1 answer
What happens if you return only -1 and 1bute not 0 java
Java
5 votes130 views2 answers
Get columns number sql
Java
2 votes145 views1 answer
How to find the length of an array in java
Java
8 votes141 views6 answers
Print list in java
Java
0 vote141 views2 answers
Detect bluetooth headphones android programmatically
Java
1 vote131 views2 answers
Scanner_Java
Java