# Java solutions with dynamic programming and DFS

• First, calculate the sum of all.
Second, if sum is odd, could not split the array.
Then, using dynamic programming, check whether we could generate subarray accumulating to sum / 2. dp[num][j] means whether we could create a subarray of items 1 ... j with the sum as "num".
Final, return dp[sum / 2][n].

``````    public boolean canPartition (int[] nums) {
int n = nums.length;
int sum = 0;

for (int i = 0; i < n; i++)
sum += nums[i];

if (sum % 2 != 0)
return false;

boolean dp[][]=new boolean[sum / 2 + 1][n + 1];

for (int i = 0; i <= n; i++) // with no item, we could get "0"
dp[0][i] = true;

for (int i = 1; i <= sum / 2; i++) // w/o item, we could not get "i"
dp[i][0] = false;

for (int i = 1; i <= sum / 2; i++) {
for (int j = 1; j <= n; j++) {
if (i >= nums[j - 1])
dp[i][j] = dp[i][j - 1] || dp[i - nums[j - 1]][j - 1]; // with or w/o item j - 1
else
dp[i][j] = dp[i][j - 1];
}
}

return dp[sum / 2][n];
}
``````

The following is the solution with DFS. It's from another post but with minor updates:

``````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 dfs(nums, 0, sum / 2);

}

public boolean dfs(int[] nums, int from, int sum) {
if(sum == 0)
return true;

if(sum < 0)
return false;

for(int i = from; i < nums.length; i++)
if(dfs(nums, i + 1, sum - nums[i]))
return true;

return false;
}
``````

• 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 dfs(nums, 0, sum / 2);

}

public boolean dfs(int[] nums, int from, int sum) {
if(sum == 0)
return true;

if(sum < 0)
return false;

for(int i = from; i < nums.length; i++)
if(dfs(nums, i + 1, sum - nums[i]))
return true;

return false;
}

time limit exceeded

• Time Limit Exceeded.

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,100]

• @nova0930 It seems to lead to infinite loop. Do you know why?

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