# Split Array With Equal Sum

• using DFS can also be accepted

``````public class Solution {
public boolean splitArray(int[] nums) {
int sum = 0, sub = 0;
for (int num : nums) sum += num;
//划分i，不能大于nums.length-5,要至少剩下5个留给剩下的三分来分
for (int i = 1; i + 5 < nums.length; i++) {
//过滤掉划分值为0的，因为重复了
if (i != 1 && nums[i - 1] == 0) continue;
sub += nums[i - 1];
if (dfs(nums, i + 1, sub, sum - sub - 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;
}
}
``````

• Solution O(N^2)

``````def splitArray(self, nums):
n = len(nums)
s = [0] * (n + 1)
for i in range(n): s[i + 1] = s[i] + nums[i]
def check(l, r):
return set(s[m] - s[l] for m in range(l + 1, r + 1) if s[m] - s[l] == s[r + 1] - s[m + 1])
return any(check(0, j - 1) & check(j + 1, n - 1) for j in range(n))``````

• To find positions of i,j,k in the array, just need to select i first, record the sum of first i-1 elements as testSum, use the testSum to search for j in the subarray [i:], if any then k in the subarray [j:]. If j, k are found, done. Otherwise select another i until all possible positions for i have been tested.

• DFS approach is getting accepted because of some weak test cases.

• what's the complexity of the DFS solution?

• No, I think time complexity is O(n^2log(n)) , because set.add() will cost log(n)

• @xhd2015 For HashSet , all operations is O(1) if proper hash function is applied.

• @lee215 yeah,I was wrong

• I believe the animation might be wrong? See the screenshot below:

sum[k-1] - sum[j] = 28 - 20 = 8
sum[n-1] - sum[k] = 36 - 30 = 6

8 != 6

• @aruballos Thanks for pointing it out. I have updated the animation. Please take a look.

• You miss the ending ')' in this line: if (sum[nums.length - 1] - sum[k] == sum[k - 1] - sum[j] && set.contains(sum[k - 1] - sum[j]))

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