Recursion + Memoization, Easy to Understand Java Solution (121ms)


  • 0
    P

    I personally find it easier to solve DP problems with recursion + memoization rather than generating a dp matrix and trying to figure out the rule.

    I used an integer memoization matrix (-1: false, 0: not processed, 1: true) because the algorithm should be aware of the distinction between a not processed false / processed false.

    Please feel free to leave your feedback and comments on possible improvements.

    class Solution {
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length <= 1) {
                return false;
            }
            
            int sumOfAll = 0;
            
            for(int n: nums) {
                sumOfAll += n;
            }
            
            if (sumOfAll % 2 != 0) {
                return false;
            }
            
            int target = sumOfAll / 2;
            
            int[][] memo = new int[nums.length][target + 1];
            return canSumToTarget(nums, target, 0, memo);
        }
        
        private boolean canSumToTarget(int[] nums, int target, int start, int[][] memo) {
            if (target == 0) {
                return true;
            }
            
            if (nums[start] == target) {
                return true;
            }
    
            if (start > nums.length - 1) return false;
    
            if (start == nums.length - 1) return false;
            
            if (memo[start][target] != 0) {
                if (memo[start][target] == 1) {
                    return true;
                }
                
                return false;
            }
            
            // pick/don't pick the current one
            boolean res = canSumToTarget(nums, target, start + 1, memo);
            if (nums[start] < target) {
                res |= canSumToTarget(nums, target - nums[start], start + 1, memo);
            }
    
            memo[start][target] = res ? 1 : -1;
            return res;
        }
    }
    

Log in to reply
 

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