# [548. Split Array with Equal Sum] C++_DFS + Hash Table + Set (46ms)

• ``````class Solution {
public:
bool splitArray(vector<int>& nums) {
if(nums.size() < 7) return false;
vector<int> sum(nums.size(),0);
unordered_map<int,unordered_set<int>> mp;
//position for sum-s
sum[0] = nums[0];
for(int i = 1; i < sum.size(); ++i){
sum[i] = sum[i-1] + nums[i];
}
for(int i = 0; i < nums.size(); ++i){
int total = sum[i];
if(mp.find(i) != mp.end() && mp[i].find(total) != mp[i].end()) continue;
if(dfs(nums, sum, mp, i+1, total, 1)) return true;
mp[i].insert(total);
}
return false;
}

bool dfs(vector<int>& nums, vector<int>& sum, unordered_map<int,unordered_set<int>>& mp, int i, int total, int interval){
//you should start from i+1. curtotal = total
if(interval == 4 && i == nums.size()) return true;
if(interval > 4) return false;
for(int p = i + 1; p < nums.size(); ++p){
if(sum[p] - sum[i] == total){
if(mp.find(p) != mp.end() && mp[p].find(total) != mp[p].end()) continue;
if(dfs(nums, sum, mp, p + 1, total, interval + 1)) return true;
mp[p].insert(total);
}
}
return false;
}
};``````

• @jasonshieh Great solution. Does the map save all the {index,totals} return false? and in the dfs function, is this line should be added?

``if(interval>4) return false;``

• @kupe Hi Kupe, thanks for your suggestion! That's great and I have made some updates to my code. It saves more time! Thanks

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