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


  • 0
    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;
    }
    };

  • 1
    K

    @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;

  • 0

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


Log in to reply
 

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