<p>You are given an integer array <code>nums</code>.</p>

<p>You should move each element of <code>nums</code> into one of the two arrays <code>A</code> and <code>B</code> such that <code>A</code> and <code>B</code> are non-empty, and <code>average(A) == average(B)</code>.</p>

<p>Return <code>true</code> if it is possible to achieve that and <code>false</code> otherwise.</p>

<p><strong>Note</strong> that for an array <code>arr</code>, <code>average(arr)</code> is the sum of all the elements of <code>arr</code> over the length of <code>arr</code>.</p>

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

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5,6,7,8]
<strong>Output:</strong> true
<strong>Explanation:</strong> We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have an average of 4.5.
</pre>

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

<pre>
<strong>Input:</strong> nums = [3,1]
<strong>Output:</strong> false
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 30</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        '''
        Assume we split the array A into B and C so that avg(B) == avg(C).
        It follows that avg(B) == avg(C) == avg(A)
        So we only need to find a proper subset B such that avg(B) == avg(A) and we can just put the remaining elements in C.
        Now if avg(B)==avg(A), that means sum(B) / B.length == sum(A) / N
        or, sum(B) == sum(A) * B.length / N

        That means we need to find a subset B, such that its sum and length satisfies this condition.

        '''

        # A subfunction that see if total k elements sums to target
        # target is the goal, k is the number of elements in set B, i is the index we have traversed through so far
        mem = {}

        def find(target, k, i):
            # if we are down searching for k elements in the array, see if the target is 0 or not. This is a basecase
            if k == 0: return target == 0

            # if the to-be selected elements in B (k) + elements we have traversed so far is larger than total length of A
            # even if we choose all elements, we don't have enough elements left, there should be no valid answer.
            if k + i > len(A): return False

            if (target, k, i) in mem: return mem[(target, k, i)]

            # if we choose the ith element, the target becomes target - A[i] for total sum
            # if we don't choose the ith element, the target doesn't change
            mem[(target - A[i], k - 1, i + 1)] = find(target - A[i], k - 1, i + 1) or find(target, k, i + 1)

            return mem[(target - A[i], k - 1, i + 1)]

        n, s = len(A), sum(A)
        # Note that the smaller set has length j ranging from 1 to n//2+1
        # we iterate for each possible length j of array B from length 1 to length n//2+1
        # if s*j%n, which is the sum of the subset, it should be an integer, so we only proceed to check if s * j % n == 0
        # we check if we can find target sum s*j//n (total sum of j elements that sums to s*j//n)

        # s is the sum of A
        # j is the length of the subarray we are looking for
        # we are checking to see if we can find j elements that sum to (j*s//n)
        # this means that the average value of the subarray is the average of A

        return any(find(s * j // n, j, 0) for j in range(1, n // 2 + 1) if s * j % n == 0)
54380