# Java solution, DFS

• Just think this problem as a DFS. What we need is to search for `3` positions (i, j, k) and see if they divide the array to `4` parts with same summary. Some tricks:

1. Calculate `left` on the fly. Thus at last we don't need to calc summary of the `4th` part.
2. Skip `0` during calculate `target` because adding zero won't change it.
``````public class Solution {
public boolean splitArray(int[] nums) {
int sum = 0, target = 0;
for (int num : nums) sum += num;
for (int i = 1; i + 5 < nums.length; i++) {
if (i != 1 && nums[i - 1] == 0  && nums[i] == 0) continue;
target += nums[i - 1];
if (dfs(nums, i + 1, target, sum - target - nums[i], 1)) return true;
}
return false;
}

private boolean dfs(int[] nums, int start, int target, int left, int depth) {
if (depth == 3) {
if (left == target) return true;
return false;
}

int sub = 0;
for (int j = start + 1; j + 5 - depth * 2 < nums.length; j++) {
sub += nums[j - 1];
if (sub == target) {
if (dfs(nums, j + 1, target, left - sub - nums[j], depth + 1)) {
return true;
}
}
}

return false;
}
}
``````

• Good Solution, Thanks!

• @shawngao
Although the test cases can be passed, I don't think the trick of skipping 0 would be correct because that will ignore the possible split point right after 0. For example, this simple test case [0,0,1,0,1,0,1,0] will lead to incorrect result. I came up with this because I wrote something similar to you but got time limit exceeded... -_-!

• @polarvenezia Thanks for pointing out the bug. Just fixed that by adding another condition `&& nums[i] == 0`

• @shawngao Yes that will make a lot more sense! Nice solution.

• I came up with the similar idea but afterwards I realized it is an O(n^3) solution, although you got AC through the 'skipping 0' trick. Basically, an O(n^2) solution with hash table may do a better job.

• Similar Idea and borrowed your idea to skip 0.

``````public boolean splitArray(int[] nums) {
if (nums.length < 6) {
return false;
}
int target = 0;
int c = 3;
for (int i = 0; i + c * 2 < nums.length; i++) {
if (i < nums.length - 1 && nums[i + 1] == 0  && nums[i] == 0) continue;
target += nums[i];
if (helper(nums, i + 2, target, c - 1)) {
return true;
}
}
return false;
}

public boolean helper(int[] nums, int start, int target, int c) {
if (start > nums.length && c == -1) {
return true;
} if (c < 0) {
return false;
}
int sum = 0;
for (int i = start; i + c * 2 < nums.length; i++) {
sum += nums[i];
if (sum == target && helper(nums, i + 2, target, c - 1)) {
return true;
}
}
return false;
}``````

• Is the time complexity O(n^3)?
It seems that the optimization is to skip continuous 0s. What if replacing 0 with -1 1 pairs? For example,
[1 -1 1 -1 1 -1 1 -1 1 -1 .... 1 1 1 1 1 1 1]

• Trick no. 2 is so important that my similar solution beat 95+% but TLE without it. Thanks a lot man.

• @zestypanda Seems like it's worse case O(n^3) and hard to avoid with this approach. I think that zero skipping trick is designed for specific test cases (e.g. no. 115 which I previously stuck at). It's legit to do so though.

• @JasonX By the end, we are targeting interviews instead of test cases.

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