Link: https://leetcode.com/problems/check-if-it-is-possible-to-split-array/description/
## 思路
一开始的做法是brute force recursion
但是会TLE
正确思路参考[这里](https://leetcode.com/problems/check-if-it-is-possible-to-split-array/solutions/3869925/java-c-python-easy-and-concise/)
This case is only possible **if there are two consecutive number whose sum is greater than or equal to m**. Because if we have this case then we can simply remove all previous and post numbers one by one. But if this is not present then there is no way we can divide all the elements as at some point we arrive at point where we have three numbers left and non of the two consecutive sum greater than or equal to m.
## Code

class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        return len(nums)<=2 or any(nums[i]+nums[i+1]>=m for i in range(len(nums)-1))

DFS+Memorization TLE

class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        prefixSum = [0]
        for num in nums:
            prefixSum.append(prefixSum[-1]+num)

        @lru_cache
        def canSplit(left, right):
            if right-left==0: return True
            for i in range(left, right):
                if validSubarray(left, i) and validSubarray(i+1, right):
                    if canSplit(left, i) and canSplit(i+1, right):
                        return True
            return False

        def validSubarray(left, right):
            return  right-left==0 or prefixSum[right+1]-prefixSum[left]>=m

        return canSplit(0, len(nums)-1)