# Why is my java solution TLE?

• I learned from discussion that this problem can be solved by a method from 0/1 knapsack problem. I use map<int, map> to simulate a 2D array, and I used a recursive style of method to accelerate the algorithm (hopefully). But why does it cause TLE?

``````public class Solution {
public boolean canPartition(int[] nums) {
if (nums == null || nums.length <= 1) {
return false;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1) {
return false;
}
int n = nums.length;
Map<Integer, Map<Integer, Boolean>> dp = new HashMap<>();
return calc(nums, n, dp, n - 1, sum / 2);
}

private boolean calc(int[] nums, int n, Map<Integer, Map<Integer, Boolean>> dp, int i, int j) {
if (contains(dp, i, j)) {
return get(dp, i, j);
}
if (j < 0) {
return false;
}
if (i == 0) {
if (nums[i] == j) {
put(dp, i, j, true);
return true;
} else {
put(dp, i, j, false);
return false;
}
}
put(dp, i, j, calc(nums, n, dp, i - 1, j) || calc(nums, n, dp, i - 1, j - nums[i]));
return get(dp, i, j);
}

private boolean contains(Map<Integer, Map<Integer, Boolean>> dp, int i, int j) {
return dp.containsKey(i) && dp.get(i).containsKey(j);
}

private void put(Map<Integer, Map<Integer, Boolean>> dp, int i, int j, boolean b) {
if (!dp.containsKey(i)) {
dp.put(i, new HashMap<Integer, Boolean>());
}
dp.get(i).put(j, b);
}

private boolean get(Map<Integer, Map<Integer, Boolean>> dp, int i, int j) {
return contains(dp, i, j) ? dp.get(i).get(j) : false;
}
}
``````

• put(dp, i, j, calc(nums, n, dp, i - 1, j) || calc(nums, n, dp, i - 1, j - nums[i]));

I changed this line, now your code runs 43ms and gets accepted.

``````put(dp, i, j, calc(nums, n, dp, i - 1, j - nums[i]) || calc(nums, n, dp, i - 1, j));   // put better chance of True ahead
``````

I also tried to do some minor improvement as below, it now runs 18ms.

``````    public boolean canPartition(int[] nums) {
if (nums == null || nums.length <= 1) {
return false;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1) {
return false;
}
Map<Integer, Map<Integer, Boolean>> dp = new HashMap<>();
return calc(nums, dp, nums.length - 1, sum / 2);
}

private boolean calc(int[] nums, Map<Integer, Map<Integer, Boolean>> dp, int i, int j) {
if (contains(dp, i, j)) {
return get(dp, i, j);
}
if(j == 0) {
put(dp, i, j, true);
return true;
}
if (i == -1 || j < 0) {
put(dp, i, j, false);
return false;
}
put(dp, i, j, calc(nums, dp, i - 1, j - nums[i]) || calc(nums, dp, i - 1, j));
return get(dp, i, j);
}

private boolean contains(Map<Integer, Map<Integer, Boolean>> dp, int i, int j) {
return dp.containsKey(i) && dp.get(i).containsKey(j);
}

private void put(Map<Integer, Map<Integer, Boolean>> dp, int i, int j, boolean b) {
if (!dp.containsKey(i)) {
dp.put(i, new HashMap<Integer, Boolean>());
}
dp.get(i).put(j, b);
}

private boolean get(Map<Integer, Map<Integer, Boolean>> dp, int i, int j) {
return dp.get(i).get(j);
}
``````

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