<p>You are given an array <code>nums</code> of length <code>n</code> and an integer <code>m</code>. You need to determine if it is possible to split the array into <code>n</code> arrays of size 1 by performing a series of steps.</p>

<p>An array is called <strong>good</strong> if:</p>

<ul>
	<li>The length of the array is <strong>one</strong>, or</li>
	<li>The sum of the elements of the array is <strong>greater than or equal</strong> to <code>m</code>.</li>
</ul>

<p>In each step, you can select an existing array (which may be the result of previous steps) with a length of <strong>at least two</strong> and split it into <strong>two </strong>arrays, if both resulting arrays are good.</p>

<p>Return true if you can split the given array into <code>n</code> arrays, otherwise return false.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [2, 2, 1], m = 4</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Split <code>[2, 2, 1]</code> to <code>[2, 2]</code> and <code>[1]</code>. The array <code>[1]</code> has a length of one, and the array <code>[2, 2]</code> has the sum of its elements equal to <code>4 &gt;= m</code>, so both are good arrays.</li>
	<li>Split <code>[2, 2]</code> to <code>[2]</code> and <code>[2]</code>. both arrays have the length of one, so both are good arrays.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [2, 1, 3], m = 5</span></p>

<p><strong>Output:</strong> <span class="example-io">false</span></p>

<p><strong>Explanation:</strong></p>

<p>The first move has to be either of the following:</p>

<ul>
	<li>Split <code>[2, 1, 3]</code> to <code>[2, 1]</code> and <code>[3]</code>. The array <code>[2, 1]</code> has neither length of one nor sum of elements greater than or equal to <code>m</code>.</li>
	<li>Split <code>[2, 1, 3]</code> to <code>[2]</code> and <code>[1, 3]</code>. The array <code>[1, 3]</code> has neither length of one nor sum of elements greater than or equal to <code>m</code>.</li>
</ul>

<p>So as both moves are invalid (they do not divide the array into two good arrays), we are unable to split <code>nums</code> into <code>n</code> arrays of size 1.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [2, 3, 3, 2, 3], m = 6</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li><span class="example-io">Split <code>[2, 3, 3, 2, 3]</code> to <code>[2]</code> and <code>[3, 3, 2, 3]</code>.</span></li>
	<li><span class="example-io">Split <code>[3, 3, 2, 3]</code> to <code>[3, 3, 2]</code> and <code>[3]</code>.</span></li>
	<li><span class="example-io">Split <code>[3, 3, 2]</code> to <code>[3, 3]</code> and <code>[2]</code>.</span></li>
	<li><span class="example-io">Split <code>[3, 3]</code> to <code>[3]</code> and <code>[3]</code>.</span></li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n == nums.length &lt;= 100</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 100</code></li>
	<li><code>1 &lt;= m &lt;= 200</code></li>
</ul>

class Solution:
    def canSplitArray(self, nums: list[int], m: int) -> bool:
        self.nums = nums
        n = len( nums )
        self.m = m
        # Construct cumulative sum for "nums" to speed up interval sums
        cum = 0
        self.cum_nums_sums = []
        for num in nums:
            cum += num
            self.cum_nums_sums.append( cum )
        # OK, Hint says Dynamic Programming, so...
        #   cSA( start_index, stop_index, n ) =>
        start_index = 0
        stop_index = n
        result = self.cSA( start_index, stop_index )
        return result

    @lru_cache( 2_000_000 )
# Return True iff the subarray nums[start_index : stop_index ] is "good"
    def cSA(self, start_index, stop_index):
        # Base case, we've reduced to a singleton, which is "good"
        if stop_index - start_index == 1:
            return True
        # Recursion cases, where we try to split the subarray further:
        else:
            result = False
            #      A  B  C  D  E  F  G  H  I  J  K
            #         | start_index   |            \
            #                    split_index     stop_index
            if True:
                for split_index in range(start_index, stop_index - 1 ):
                    low_len = split_index + 1 - start_index
                    low_sum = self.cum_nums_sums[ split_index ] - ( 0 if start_index == 0 else self.cum_nums_sums[ start_index - 1 ] )
                    if ( low_len > 1 and low_sum < self.m ):
                        continue
                    high_len = stop_index - split_index - 1
                    high_sum = sum( self.nums[ split_index  + 1: stop_index ])
                    high_sum = self.cum_nums_sums[ stop_index - 1 ] - self.cum_nums_sums[ split_index ]
                    if  high_len > 1 and high_sum < self.m :
                        continue
                    result = (self.cSA(start_index, split_index + 1 ) and
                              self.cSA(split_index + 1, stop_index))
                    if result:
                        break
        return result

2517