Partition Equal Subset Sum (optimised)

// Que  Partition Equal Subset Sum

// Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

// Input: nums = [1,5,11,5]
// Output: true
// Explanation: The array can be partitioned as [1, 5, 5] and [11].

//  Link -- https://leetcode.com/problems/partition-equal-subset-sum/



class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        
        return help(0,nums,sum/2, new HashMap<String, Boolean>());
    }
    
    private static boolean help(int currPos, int []arr, int sum, HashMap<String,Boolean> memo){
        if(sum==0){
            return true;
        }
        if(currPos>=arr.length){
            return false;
        }
        
        String key = Integer.toString(currPos)+"-"+Integer.toString(sum);
        
        if(memo.containsKey(key)){
            return memo.get(key);
        }
        
        boolean consider = false;
        boolean notConsider = false; 
        
        if(sum>=arr[currPos]){
             consider = help(currPos+1, arr, sum-arr[currPos],memo);
        }
       
        if(consider!=true){
            notConsider = help(currPos+1, arr, sum,memo);
        }
        
        
        boolean ans =  consider|| notConsider;
        memo.put(key,ans);
        return memo.get(key);
    }
}