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

• 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.

``````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;
}
}
``````

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