Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.1 kB
2
Indexable
Never
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)):
            if i == 0:
                cum_sum[i+1] = nums[i]
            else:
                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)