In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)
Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.
Example :
Input: 
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.
Note:
The length of A will be in the range [1, 30].
A[i] will be in the range of [0, 10000].
from functools import lru_cache

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        # TLE
#         avg = sum(A) / len(A)
#         for k in range(1, len(A) // 2 + 1):
#             for comb in combinations(A, k):
#                 if abs(sum(comb) / k - avg) < 1e-5:
#                     return True
            
#         return False

        N, S = len(A), sum(A)
        
        @lru_cache(None)
        def combinationSum(target, start, k):
            if target == 0:
                return k == 0
            if start == N or k < 0 or target < 0:
                return False
            
            return combinationSum(target-A[start], start+1, k-1) or combinationSum(target, start+1, k)
        
        for k in range(1, N // 2 + 1):
            if S * k % N == 0:
                if combinationSum(S * k // N, 0, k):
                    return True
        
        return False
from functools import lru_cache

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        # TLE
#         avg = sum(A) / len(A)
#         for k in range(1, len(A) // 2 + 1):
#             for comb in combinations(A, k):
#                 if abs(sum(comb) / k - avg) < 1e-5:
#                     return True
            
#         return False

        N, S = len(A), sum(A)
        
        @lru_cache(None)
        def combinationSum(target, start, k):
            if target == 0:
                return k == 0
            if start == N or k < 0 or target < 0:
                return False
            
            return combinationSum(target-A[start], start+1, k-1) or combinationSum(target, start+1, k)
        
        for k in range(1, N // 2 + 1):
            if S * k % N == 0:
                if combinationSum(S * k // N, 0, k):
                    return True
        
        return False