# 69ms JAVA SuperFast solution with Explanation

• First I tried the top-down recursive approach no memoization... solution was easy but I couldn't pass the TLE.

``````public class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
int len = nums.length;
if (len < 2) {
return false;
}
Arrays.sort(nums);
for (int i = 0; i < len; i++) {
sum += nums[i];
}
if (sum % 2 != 0) {
return false;
}
return canPartitionHelper(nums, sum / 2);
}

private boolean canPartitionHelper(int[] nums, int target) {
return helper2(nums, 0, 0, target);
}

private boolean helper2(int[] nums, int curr, int currPos, int target) {
if (curr == target) {
return true;
}
if (currPos == nums.length) {
return false;
}

return helper2(nums, curr + nums[currPos], currPos + 1, target) ||
helper2(nums, curr, currPos + 1, target);

}
}
``````

So I wrote the dp (bottom-up) version which is similar to knapsack 01 solution but breaking the execution if there is a solution found.

``````     private boolean canPartitionHelper(int[] nums, int target) {
int len = nums.length;
int[][] dp = new int[len + 1][target + 1];
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= target; j++) {
if (nums[i - 1] == target) {
return true; // the solution is this number by itself and the rest
} else if (nums[i - 1] > target) {
return false; // there is no way we can get the solution
}

if (dp[i - 1][j] == target) {
return true; // the solution was found let's return
}
if (j - nums[i - 1] >= 0) { // normal dp similar to Knapsack 01
dp[i][j] = dp[i - 1][j - nums[i - 1]] + nums[i - 1];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[len][target] == target;
}
``````

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