class Solution {
    Boolean[][] arr;
    public boolean canPartition(int[] nums) {
        int total = 0;
        for(int i=0; i<nums.length; i++) {
            total = total + nums[i];
        }
        if(total % 2 == 1)
            return false;
        
        arr = new Boolean[total+1][nums.length+1];
        return canPartitionAux(nums, total, 0, 0);
    }
    
    public Boolean canPartitionAux(int[] nums, int total, int currTotal, int i) {
        if(arr[currTotal][i] != null) {
            return arr[currTotal][i];
        }
        
        if(i == nums.length) {
            return false;
        }
        
        if(currTotal > (total/2)) {
            return false;
        }
        
        if(currTotal == total/2) {
            return true;
        }
        
        arr[currTotal][i] = canPartitionAux(nums, total, currTotal + nums[i], i+1) 
            || canPartitionAux(nums, total, currTotal, i+1);;
        return arr[currTotal][i];            
    }
}