class Solution:
def canSplitArray(self, nums: List[int], m: int) -> bool:
if len(nums) <= 2:
return True
cum_sum = [0] * (len(nums)+1)
for i in range(len(nums)):
cum_sum[i+1] = nums[i] + cum_sum[i]
memo = dict()
def helper(low, high):
if (high - low) == 0:
memo[(low, high)] = True
return True
if (cum_sum[high+1] - cum_sum[low]) < m:
memo[(low, high)] = False
return False
if (low, high) in memo:
return memo[(low, high)]
for i in range(low, high):
if helper(low, i) and helper(i+1, high):
memo[(low, high)] = True
return True
memo[(low, high)] = False
return False
return helper(0, len(nums)-1)