Description

Submission

class Solution {

    unordered_map<int, bool> mem;
    bool dfs(vector<int>& nums, int m, int a, int b) {
        if (mem.find((a<<16)+b) != mem.end()) return mem[(a<<16)+b];

        if (a + 1 == b) return true;

        if (accumulate(nums.begin() + a, nums.begin() + b, 0) < m) {
            mem[(a<<16)+b] = false;
            return false;
        }
        
        for(int i = a + 1; i < b; ++i) {
            if(dfs(nums, m, a, i) && dfs(nums, m, i, b)) {
                mem[(a<<16)+b] = true;
                return true;
            }
        }

        mem[(a<<16)+b] = false;
        return false;
    }
public:
    bool canSplitArray(vector<int>& nums, int m) {
        if (nums.size() == 1) return true;

        for (int i = 0; i < nums.size(); ++i) {
            if (dfs(nums, m, 0, i) && dfs(nums, m, i, nums.size())) return true;
        }
        return false;
    }
};

class Solution {

public:
    bool canSplitArray(vector<int>& nums, int m) {
        if (nums.size() < 3) return true;

        for (int i = 0; i < nums.size() - 1; ++i) {
            if (nums[i] + nums[i+1] >= m) return true;
        }

        return false;
    }
};