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].

Difficulty: interview

Starter code:

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        

Solutions:
class Solution:
    def splitArraySameAverage(self, A):
        N, S = len(A), sum(A)
        if N == 1: return False
        A = [z * N - S for z in A] 
        mid, left, right = N//2, {A[0]}, {A[-1]}


        if not any((S*size) % N == 0 for size in range(1, mid+1)): return False

        for i in range(1, mid): left |= {z + A[i] for z in left} | {A[i]}
        for i in range(mid, N-1): right |= {z + A[i] for z in right} | {A[i]}
        if 0 in (left|right): return True


        left -= {sum(A[:mid])}
        return any(-ha in right for ha in left)

class Solution:
    def splitArraySameAverage(self, A):
        N, S, P = len(A), sum(A), [1]
        for a in A:
            P[1:] = [(p << a) | q for p, q in zip(P, P[1:] + [0])]
        return any(S * n % N == 0 and P[n] & (1 << (S * n // N))
               for n in range(1, N))

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        tot = sum(A)
        n = len(A)
        target = tot/n 
        visited = [ False]*len(A)
        m = n // 2
        possible = False
        for i in range(1, m+ 1):
            if (tot * i)%n == 0:
                possible = True
                break
        if not possible:
            return False
        A.sort( )
        
        
        def helper(A, cursum, curcnt, pos):
            if curcnt == 0:
                return cursum == 0
            
            for i in range(pos, len(A) - curcnt + 1):
                if i > pos and A[i]==A[i-1]:
                    continue
                if helper(A, cursum - A[i], curcnt - 1, i + 1):
                    return True
            
            return False
         
        for i in range(1, m + 1):
            if (tot * i)%n == 0 and helper(A, (tot * i)/n, i, 0):
                return True
        return False
            
            


# from functools import lru_cache
# class Solution:
#     def splitArraySameAverage(self, A: List[int]) -> bool:
#         # A.sort(reverse=True)
#         n, total = len(A), sum(A)
#         avag = total/n
#         # epsilon = 0.000001
#         # print(avag)
#         @lru_cache(None)
#         def dfs(idx, sums, sz):
#             if 0 < sz <= n//2 and total*sz%n == 0 and sums == total*sz//n:
#                 return True
#             if idx == n or sz > n//2 or sums > total/2:
#                 return False
            
#             return dfs(idx+1, sums+A[idx], sz+1) or dfs(idx+1, sums, sz)
#             # print(idx,sums,sz,res)
#         return dfs(0,0,0)

from functools import lru_cache
class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        n, total = len(A), sum(A)
        @lru_cache(None)
        def dfs(idx, target, sz):
            if target < 0 or idx+sz > n:
                return False
            if sz == 0 or idx  == n:
                return target == 0
            
            
            
            return dfs(idx+1, target-A[idx], sz-1) or dfs(idx+1, target, sz)
            # print(idx,sums,sz,res)
        return any(dfs(0,total*k//n,k) for k in range(1,n//2+1) if total*k%n == 0)

# from functools import lru_cache
# class Solution:
#     def splitArraySameAverage(self, A: List[int]) -> bool:
#         # A.sort(reverse=True)
#         n, total = len(A), sum(A)
#         avag = total/n
#         # epsilon = 0.000001
#         # print(avag)
#         @lru_cache(None)
#         def dfs(idx, sums, sz):
#             if 0 < sz <= n//2 and total*sz%n == 0 and sums == total*sz//n:
#                 return True
#             if idx == n or sz > n//2 or sums > total/2:
#                 return False
            
#             return dfs(idx+1, sums+A[idx], sz+1) or dfs(idx+1, sums, sz)
#             # print(idx,sums,sz,res)
#         return dfs(0,0,0)

from functools import lru_cache
class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        n, total = len(A), sum(A)
        @lru_cache(None)
        def dfs(idx, target, sz):
            
            if target < 0 or idx+sz > n:
                return False
            if sz == 0:
                return target == 0
            
            
            return dfs(idx+1, target-A[idx], sz-1) or dfs(idx+1, target, sz)
            # print(idx,sums,sz,res)
        return any(dfs(0,total*k//n,k) for k in range(1,n//2+1) if total*k%n == 0)

# from functools import lru_cache
# class Solution:
#     def splitArraySameAverage(self, A: List[int]) -> bool:
#         # A.sort(reverse=True)
#         n, total = len(A), sum(A)
#         avag = total/n
#         # epsilon = 0.000001
#         # print(avag)
#         @lru_cache(None)
#         def dfs(idx, sums, sz):
#             if 0 < sz <= n//2 and total*sz%n == 0 and sums == total*sz//n:
#                 return True
#             if idx == n or sz > n//2 or sums > total/2:
#                 return False
            
#             return dfs(idx+1, sums+A[idx], sz+1) or dfs(idx+1, sums, sz)
#             # print(idx,sums,sz,res)
#         return dfs(0,0,0)

from functools import lru_cache
class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        n, total = len(A), sum(A)
        @lru_cache(None)
        def dfs(idx, target, sz):
            if sz == 0:
                return target == 0
            if target < 0 or idx+sz > n:
                return False
            
            
            
            return dfs(idx+1, target-A[idx], sz-1) or dfs(idx+1, target, sz)
            # print(idx,sums,sz,res)
        return any(dfs(0,total*k//n,k) for k in range(1,n//2+1) if total*k%n == 0)

from functools import lru_cache
class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:

        # mem = {}
        @lru_cache(None)
        def find(target, k, i):

            if k == 0: return target == 0

            if k + i > len(A): return False

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


            ans = find(target - A[i], k - 1, i + 1) or find(target, k, i + 1)

            return ans

        n, s = len(A), sum(A)

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


# from functools import lru_cache
# class Solution:
#     def splitArraySameAverage(self, A: List[int]) -> bool:
#         # A.sort(reverse=True)
#         n, total = len(A), sum(A)
#         avag = total/n
#         # epsilon = 0.000001
#         # print(avag)
#         @lru_cache(None)
#         def dfs(idx, sums, sz):
#             if 0 < sz <= n//2 and total*sz%n == 0 and sums == total*sz//n:
#                 return True
#             if idx == n or sz > n//2 or sums > total/2:
#                 return False
            
#             return dfs(idx+1, sums+A[idx], sz+1) or dfs(idx+1, sums, sz)
#             # print(idx,sums,sz,res)
#         return dfs(0,0,0)

from functools import lru_cache
class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        n, total = len(A), sum(A)
        @lru_cache(None)
        def dfs(idx, target, sz):
            if sz < 0 or target < 0 or idx+sz > n:
                return False
            if idx == n:
                return target == 0
            
            
            return dfs(idx+1, target-A[idx], sz-1) or dfs(idx+1, target, sz)
            # print(idx,sums,sz,res)
        return any(dfs(0,total*k//n,k) for k in range(1,n//2+1) if total*k%n == 0)

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        if len(A) < 2:
            return False
        
        sumA, lenA = sum(A), len(A)
        
        if sumA / lenA in A:
            return True
        
        if len(A) < 3:
            return False
        
        if not any((sumA*size) % lenA == 0 for size in range(1, lenA//2+1)): 
            return False
        
        A = [i * lenA - sumA for i in A]
        A.sort()
        
        a = [i for i in A if i < 0]
        b = [i for i in A if i > 0]
        
        if len(a) > len(b):
            a, b = b, a
        
        d = set()
        def r1(s, arr, n):
            xx = None
            while arr:
                x = arr.pop()
                if xx == x:
                    continue
                
                xx = x
                ss = s + x
                
                d.add(-ss)
                
                if n:
                    r1(ss, list(arr), n-1)

        r1(0, a, len(a) // 2)
        
        def r2(s, arr, n):
            xx = None
            while arr:
                x = arr.pop()
                if xx == x:
                    continue
                
                xx = x
                ss = s + x
                if ss in d:
                    return True
                
                if n and r2(ss, list(arr), n-1):
                    return True
        return r2(0, b, len(b) // 2 - 1)



            


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        # fix how many go into B and C
        # then we know what the goal is?
        # 4:1, B gets 4x as much as C
        # B gets 4/5, C gets 1/5
        # then knapsack on one of them (lower one)
        A.sort(reverse=True)
        def helper(goal,cnt):
            # knapsack
            @lru_cache(None)
            def dp(i,tot,left):
                if tot==goal and left==0:
                    return True
                if tot>goal or left==0 or i==len(A):
                    return False
                return dp(i+1,tot,left) or dp(i+1,tot+A[i],left-1)
            return dp(0,0,cnt)
        tot = sum(A)
        for i in range(1,len(A)//2+1):
            # B gets i
            # C gets len(A)-i
            # B gets i/len(A) * tot
            needed = tot*i/len(A)
            if int(needed)!=needed:
                continue
            needed=int(needed)
            if helper(needed,i):
                print(needed)
                return True
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        m = len(A)
        total = sum(A)
        target = total / m
        A.sort()
        
        @lru_cache(None)
        def dfs(k, i, sum_b):
            if k == 0:
                return sum_b == 0
            if i == len(A):
                return False
            return dfs(k - 1, i + 1, sum_b - A[i]) or dfs(k, i + 1, sum_b)
        
        for k in range(1, m // 2 + 1):
            if total * k % m == 0:
                if dfs(k, 0, total * k // m):
                    return True
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        def dp(idx, L, target):
            if L==0 and target==0:
                return True
            
            if idx==N or L==0 or target<0:
                return False
            
            if (idx, L, target) in memo: return memo[(idx, L, target)]
            memo[(idx, L, target)] = A[idx]<=target and dp(idx+1, L-1, target-A[idx]) or dp(idx+1, L, target)
            return memo[(idx, L, target)]       

        total = sum(A)
        N = len(A)
        
        for i in range(1, len(A)//2+1):
            sub_sum = total*i/N
            memo = {}
            if sub_sum == int(sub_sum) and dp(0, i, int(sub_sum)):
                return True
            
        return False


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        S = sum(A)
        N = len(A)
        A.sort(reverse = True)
        import functools
        @functools.lru_cache(None)
        def DFS(target,i,n_left):
            if target == 0 :
                return (n_left == 0)
            if target < 0 :
                return False
            if i == len(A):
                return False
            return DFS(target-A[i],i+1,n_left-1) or DFS(target,i+1,n_left)
        
        
        return any(DFS(S*K//N,0,K) for K in range(1,N) if S*K%N == 0)


class Solution:
    def splitArraySameAverage(self, nums):
        def find(target, k, i):
            if (target, k) in d and d[(target, k)] <= i:
                return False
            if k == 0:
                return target == 0
            if k + i > len(nums):
                return False
            res = find(target - nums[i], k - 1, i + 1) or find(target, k, i + 1)
            if not res:
                d[(target, k)] = min(d.get((target, k), length), i)
            return res

        d, length, sum_nums = {}, len(nums), sum(nums)
        return any(
            find(sum_nums * i // length, i, 0) 
            for i in range(1, length // 2 + 1) 
            if sum_nums * i % length == 0
                )

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

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        la = len(A)
        sa = sum(A)
       
        memo = {}
        
        def find(target,k,i): # k is needed length, i is the ith element
            if k==0: return target==0
            if k+i>la: return False
         
            if (target,k,i) in memo: return memo[(target,k,i)]
            
            memo[(target,k,i)] = find(target-A[i],k-1,i+1) or find(target,k,i+1)
            return memo[(target,k,i)]
        
        return any(find(j*sa//la,j,0) for j in range(1,la//2+1) if j*sa%la==0)


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        import sys
        from functools import lru_cache
        
    
    
        @lru_cache(None)
        def knapsack(i, num, tot):
            # Find num items in A that add up to tot
            if i > len(A) - 1 or num <= 0 or tot <= 0:
                return False
            elif num == 1 and A[i] == tot:
                return True
            else:
                include = knapsack(i + 1, num - 1, tot - A[i])
                exclude = knapsack(i + 1, num, tot)

                if include:
                    return True
                elif exclude:
                    return True
            return None
        sys.setrecursionlimit(100000)
        tot = sum(A)
        n = len(A)

        gcd = math.gcd(tot, n)

        num = n // gcd
        A = sorted(A)

        for i in range(1,n):
            if (tot*i)%n == 0:
                k = knapsack(0, i, tot * i // n)
                if k is not None:
                    return True
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        memo = {}
        
        def dfs(k, idx, total):
            if k == 0: return total == 0
            if k + idx > len(A): return False
            
            if (k, idx, total) in memo: return memo[(k, idx, total)]
            
            pick = dfs(k - 1, idx + 1, total - A[idx])
            not_pick = dfs(k, idx + 1, total)
            
            memo[(k-1, idx+1, total - A[idx])] = pick or not_pick
            return pick or not_pick
        n, s = len(A), sum(A)
        for k in range(1, n // 2 + 1):
            if k * s % n == 0 and dfs(k, 0, k * s // n):
                return True
        return False

class Solution:
#def splitArraySameAverage(self, A: List[int]) -> bool:
    def splitArraySameAverage(self, A: List[int]) -> bool:

    # 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)
        return any(find(s * j // n, j, 0) for j in range(1, n // 2 + 1) if s * j % n == 0)


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        S = sum(A)
        N = len(A)
        A.sort()
        import functools
        @functools.lru_cache(None)
        def DFS(target,i,n_left):
            if target == 0 :
                return (n_left == 0)
            if i == len(A) or target < 0 or target-A[i]*n_left < 0:
                return False
            return DFS(target-A[i],i+1,n_left-1) or DFS(target,i+1,n_left)
        
        
        return any(DFS(S*K//N,0,K) for K in range(1,N) if S*K%N == 0)


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:

        memo = {}
        
        def dfs(idx, k, total) -> bool:
            #base case
            if k == 0: return total == 0
            if k + idx > len(A): return False
            if (idx, k, total) in memo: return memo[(idx, k, total)]
            
            #pick or not pick
            memo[(idx+1, k-1, total-A[idx])] = dfs(idx+1, k-1, total-A[idx]) or dfs(idx+1, k, total)
            return memo[(idx+1, k-1, total-A[idx])]
            
        s, n = sum(A), len(A)
        
        #to check k*s is interger
        return any(dfs(0, k, k*s//n) for k in range(1, n//2 + 1) if k*s%n == 0)


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:

        memo = {}
        
        def dfs(idx, k, total) -> bool:
            
            if k == 0: return total == 0
            if idx + k > len(A): return False
            if (idx, k, total) in memo: return memo[(idx, k, total)]
            
            #pick or not pick
            memo[(idx+1, k-1, total-A[idx])] = dfs(idx+1, k-1, total-A[idx]) or dfs(idx+1, k, total)
            
            return memo[(idx+1, k-1, total-A[idx])]
            
        
        s, n = sum(A), len(A)
        #(s//n) is the average
        return any(dfs(0, k, k * s//n) for k in range(1, n // 2 + 1) if k * s % n == 0)
        


class Solution:
    def dp(self, A, index, sum_, size, aux, dp):
        if index == len(A): return False
        if size == 0: return sum_ == 0

        key = str(index) + str(sum_) + str(size)
        if key in dp:
            return dp[key]

        if A[index] <= sum_:
            aux.append(A[index])
            if self.dp(A,index+1, sum_-A[index], size - 1, aux, dp):
                dp[key] = True
                return dp[key]
            aux.pop()

        if self.dp(A, index+1, sum_, size, aux, dp):
            dp[key] = True
            return dp[key]

        dp[key] = False
        return dp[key]
    
    def splitArraySameAverage(self, A: List[int]) -> bool:
        n = len(A)
        sum_ = sum(A)
        dp = {}
        ans = []
        tmp1 = A
        for i in range(1,n):
            if (sum_ * i) % n == 0:
                s1 = sum_*i
                s1 //= n
                aux = []
                if self.dp(A,0, s1, i, aux, dp):
                    return True
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        memo = {}
        
        def dfs(total, k, idx) -> bool:
            if k == 0: return total == 0
            if k + idx > len(A): return False
            
            if (total, k, idx) in memo: return memo[(total, k, idx)]
            
            #pick
            pick = dfs(total - A[idx], k-1, idx+1)
            not_pick = dfs(total, k, idx+1)
            
            memo[(total - A[idx], k-1, idx+1)] = pick or not_pick
            return memo[(total - A[idx], k-1, idx+1)] 
        
        n, s = len(A), sum(A)
        
        return any(dfs(s * k // n, k, 0) for k in range(1, n//2 + 1) if k * s % n == 0)

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        A_sum = float(sum(A))
        max_sublen = len(A) // 2
        
        targets = {}
        last_valid_target = None
        for i in range(1, max_sublen+1):
            target = A_sum*i/len(A)
            if target % 1 == 0:
                last_valid_target = int(target)
                targets[last_valid_target] = i
                
        if last_valid_target is None:
            return False
                
        dp = [set() for _ in range(last_valid_target+1)]
        dp[0].add(0)
        for i in range(len(A)):
            for sum_ in range(last_valid_target, A[i]-1, -1):
                set2 = dp[sum_-A[i]]
                if A[i] == 0:
                    set2 = dp[sum_-A[i]].copy()
                for n in set2:
                    dp[sum_].add(n+1)
                    if sum_ in targets and targets[sum_] == n+1:
                        #print(dp)
                        #print(sum_, n+1)
                        return True
        
        return False


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        def dp(idx, rem, cnt):
            if cnt==0 and rem==0:
                return True
            
            if idx==N or cnt==0 or rem==0:
                return False
            
            if (idx, rem, cnt) in memo: return memo[(idx, rem, cnt)]
            
            res = False
            for i in range(idx, N):
                if A[i]>rem: break
                if dp(i+1, rem-A[i], cnt-1):
                    res = True
                    break
            
            memo[(idx, rem, cnt)] = res
            return res
        
        suma = sum(A)
        N = len(A)
        memo = {}
        A.sort()
        for i in range(1, N//2+1):
            if suma*i%N==0 and dp(0, suma*i/N, i):
                return True
            
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        mem = {}

        def find(target, k, i):
            if k == 0: 
                return target == 0

            if k + i > len(A): 
                return False

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

           
            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)
       
        return any(find(s * j // n, j, 0) for j in range(1, n // 2 + 1) if s * j % n == 0)


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        A.sort()
        DP=[set() for _ in range(len(A)//2+1)]    #DP[i] stores the all available sum with i items in a bracket
        all_sum=sum(A)
        DP[0]=set([0])
        for item in A:                  #iterate over items in the list
            for count in range(len(DP)-2,-1,-1):          # iterate backwards w.r.t. the bracket size
                if len(DP[count])>0:                             # if DP[i] is not empty, then update DP[i+1] by adding the current item into all sums in DP[i]
                    for a in DP[count]:
                        DP[count+1].add(a+item)
        for size in range(1,len(DP)):
            if all_sum*size/len(A) in DP[size]:
                return True
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        n = len(A)
        k = int(n/2)
        dp = [set() for i in range(k+1)]
        dp[0].add(0)
        
        for i,v in enumerate(A):
            for j in range(min(i+1,k),0,-1):
                for m in dp[j-1]:
                    dp[j].add(m+v)
        total = sum(A)
        for i in range(1,k+1):
            if total * i % n == 0:
                if (i * total / n) in dp[i]:
                    return True
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        n = len(A)
        k = int(n/2)
        dp = [set() for i in range(k+1)]
        dp[0].add(0)
        for i,v in enumerate(A):
            for j in range(min(i+1,k),0,-1):
                for m in dp[j-1]:
                    dp[j].add(m+v)
        
        total = sum(A)
        for i in range(1,k+1):
            if i * total % n == 0:
                if (total * i / n) in dp[i]:
                    return True
        return False

#class Solution:
#    def splitArraySameAverage(self, A: List[int]) -> bool:
class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        A.sort()
        DP=[set() for _ in range(len(A)//2+1)]    #DP[i] stores the all available sum with i items in a bracket
        all_sum=sum(A)
        DP[0]=set([0])
        for item in A:                  #iterate over items in the list
            for count in range(len(DP)-2,-1,-1):          # iterate backwards w.r.t. the bracket size
                if len(DP[count])>0:                             # if DP[i] is not empty, then update DP[i+1] by adding the current item into all sums in DP[i]
                    for a in DP[count]:
                        DP[count+1].add(a+item)
        for size in range(1,len(DP)):
            if all_sum*size/len(A) in DP[size]:
                return True
        return False

from collections import defaultdict
class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        total = sum(A)
        size = len(A)
        possible = False
        for i in range(size//2):
            if total*i % size == 0:
                possible = True
                break
        if not possible:
            return False
        dp = defaultdict(set)
        dp[0].add(0)
        for n in A:
            for i in range(size//2, 0, -1):
                for ele in dp[i-1]:
                    dp[i].add(ele+n)
        for i in range(1, size//2+1):
            if total*i % size == 0 and total*i//size in dp[i]:
                return True
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        A.sort()
        DP=[set() for _ in range(len(A)//2+1)]    #DP[i] stores the all available sum with i items in a bracket
        all_sum=sum(A)
        DP[0]=set([0])
        for item in A:                  #iterate over items in the list
            for count in range(len(DP)-2,-1,-1):          # iterate backwards w.r.t. the bracket size
                if len(DP[count])>0:                             # if DP[i] is not empty, then update DP[i+1] by adding the current item into all sums in DP[i]
                    for a in DP[count]:
                        DP[count+1].add(a+item)
        for size in range(1,len(DP)):
            if all_sum*size/len(A) in DP[size]:
                return True
        return False


from functools import lru_cache
class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        A.sort()
        @lru_cache(None)
        def dfs(idx, n, target):
            if target == 0 and n == 0:
                return True
            if idx >= len(A) or n == 0:
                return False
            return dfs(idx + 1, n - 1, target - A[idx]) or dfs(idx + 1, n, target)
        
        return any([dfs(0, i, (sum(A) * i) // len(A)) for i in range(1, len(A)) if (sum(A) * i) % len(A) == 0])
        


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:

        if len(A) < 3:
            return False
        
        sumA, lenA = sum(A), len(A)
        
        if sumA / lenA in A:
            return True
        
        A = [i * lenA - sumA for i in A]
        A.sort()
        
        a = [i for i in A if i < 0]
        b = [i for i in A if i > 0]
        
        if len(a) > len(b):
            a, b = b, a
        
        d = set()
        def r1(s, arr, n):
            xx = None
            while arr:
                x = arr.pop()
                if xx == x:
                    continue
                
                xx = x
                ss = s + x
                
                d.add(-ss)
                
                if n:
                    r1(ss, list(arr), n-1)

        r1(0, a, len(a) // 2)
        
        def r2(s, arr, n):
            xx = None
            while arr:
                x = arr.pop()
                if xx == x:
                    continue
                
                xx = x
                ss = s + x
                if ss in d:
                    return True
                
                if n and r2(ss, list(arr), n-1):
                    return True
        return r2(0, b, len(b) // 2 - 1)



            


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        ksums = [{0}]
        maxk = len(A) // 2
        
        for a in A:
            #print('a', a)
            #print('ksums', ksums)
            ksums = [[0]] + [
                (ksums[k] if k < len(ksums) else set()) |
                {a + x for x in ksums[k - 1]}
                for k in range(1, min(len(ksums), maxk) + 1)
            ]
            #print('ksums*', ksums)
            
        n = len(A)
        S = sum(A)
        for k in range(1, min(len(ksums), maxk) + 1):
            if any(x * (n - k) == k * (S - x) for x in ksums[k]):
                return True
        
        return False


from typing import List

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        if (len(A) <= 1):
            return False
        
        n = len(A)
        Sum = 0
        for x in A:
            Sum += x
        dp = [ 0 for _ in range(Sum+1)]
        dp[A[0]] = 2;
        for i in range(1,n):
            for s in range(Sum-A[i] , -1, -1):
                if dp[s] > 0:
                    dp[s+A[i]] |= (dp[s]<<1)
            dp[A[i]] |= 2;
        
        for leng in range(1, n):
            if (Sum*leng) % n == 0 and ( (1<<leng) & dp[(Sum*leng)//n] ):
                return True
        return False
    
    



class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        return self.dp_bitwise(A)

    def dp_bitwise(self, A: List[int]) -> bool:
        #dummy case
        if (len(A) <= 1):
            return False
        #calculate sum and number of elements
        n = len(A)
        Sum = 0
        for x in A:
            Sum += x
        #dp[s] = m -- means sum s can be formed with elements of length bit i == 1 of m
        #e.g. dp[10] = 20 it means sum 10 can be achieved with 2 or 4 elements - 10100 
        #init dp with 0
        dp = [ 0 for _ in range(Sum+1)]
        dp[A[0]] = 2
        #we iterate through all the elements
        for i in range(1, n):
            #we check every possible sum 
            for s in range(Sum-A[i], -1, -1):
                #if s can be previously formed
                if dp[s] > 0:
                    # it means we can form s + A[i] also from dp[s] by shifting it 
                    # with one, as we have an additional element
                    dp[s + A[i]] |= (dp[s]<<1)
            dp[A[i]] |= 2
        
        for leng in range(1, n):
            if (Sum * leng) % n == 0 and ( (1 << leng) & dp[(Sum * leng) // n] ):
                return True
        return False

    


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        
        N = len(A)
        
        if N <= 1:
            return False
        
        max_sum = sum(A)
        #print(max_sum)
        sums = [0] * (max_sum+1)
        for i in range(N):
            num = A[i]
            for s in range(max_sum, num-1, -1):
                if sums[s-num]:
                    sums[s] |= sums[s-num] << 1
            sums[num] |= 1
            #print(sums)
        #print(sums)
        for l in range(1, N):
            if (max_sum * l) % N == 0:
                s = int((max_sum * l) / N)
                if (sums[s] >> (l-1)) & 1:
                    return True
        return False           

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        
        N = len(A)
        
        if N <= 1:
            return False
        
        max_sum = sum(A)
        #print(max_sum)
        sums = [0] * (max_sum+1)
        for i in range(N):
            num = A[i]
            for s in range(max_sum, num-1, -1):
                if sums[s-num]:
                    sums[s] |= sums[s-num] << 1
            sums[num] |= 1
            #print(sums)
        #print(sums)
        for l in range(1, N):
            s = (max_sum * l) / N
            if s.is_integer() and (sums[int(s)] >> (l-1)) & 1:
                return True
        return False           

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        
#         ALen = len(A)
#         visited = set()
        
#         def checkNum(i0, bN, bSum, aN, aSum):
#             if i0 == ALen:
#                 if aN != 0 and bN != 0 and bSum*aN == aSum*bN:
#                     return True
#                 return False
#             if (i0, bN, bSum) in visited:
#                 return False
#             visited.add((i0, bN, bSum))
#             subAns = checkNum(i0+1, bN+1, bSum+A[i0], aN, aSum) or checkNum(i0+1, bN, bSum, aN +1, aSum + A[i0])
#             return subAns
        
#         return checkNum(0, 0, 0, 0, 0)
        from fractions import Fraction
        ALen = len(A)
        s = sum(A)
        if ALen == 1:
            return False
        
        for i in range(ALen):
            A[i] -= Fraction(s, ALen)
        A.sort()
        leftSet = {A[0]}
        for i in range(1, ALen//2):
            leftSet = {z+A[i] for z in leftSet} | leftSet | {A[i]}
        if 0 in leftSet:
            return True
        
        rightSet = {A[ALen-1]}
        for i in range(ALen//2, ALen-1):
            rightSet = {z+A[i] for z in rightSet} | rightSet | {A[i]}
        if 0 in rightSet:
            return True
        
        leftSum = sum(A[:ALen//2])
        rightSum = sum(A[ALen//2:])
        
        return any(-left in rightSet and (left, -left) != (leftSum, rightSum) for left in leftSet)

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        ksums = [{0}]
        maxk = len(A) // 2
        
        n = len(A)
        S = sum(A)
        for a in A:
            #print('a', a)
            #print('ksums', ksums)
            nksums = [[0]]
            for k in range(1, min(len(ksums), maxk) + 1):
                new_part = {a + x for x in ksums[k - 1]}
                if any(x * (n - k) == k * (S - x) for x in new_part):
                    return True
                
                row = (ksums[k] if k < len(ksums) else set()) | new_part
                nksums.append(row)
                
            ksums = nksums
            #print('ksums*', ksums)
            
        
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        total_sum = sum(A)
        sum_dict = collections.defaultdict(set)

        for val in A:
            temp_list = [(1, val)]
            for key, set_val in sorted(sum_dict.items()):
                if key == len(A) // 2:
                    break
                for sum_val in set_val:
                    temp_list.append((key + 1, val + sum_val))
            for key_val, sum_val in temp_list:
                sum_dict[key_val].add(sum_val)

        for i in range(len(A) - 1):
            if (total_sum * (i + 1) / len(A)) in sum_dict[i + 1]:
                return True
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:

        if len(A) < 3:
            return False
        
        sumA, lenA = sum(A), len(A)
        
        if sumA / lenA in A:
            return True
        
        A = [i * lenA - sumA for i in A]
        A.sort()
        
        a = [i for i in A if i < 0]
        b = [i for i in A if i > 0]
        
        if len(a) > len(b):
            a, b = b, a
        
        d = {-i for i in A}
        def r1(s, arr, n):
            xx = None
            while arr:
                x = arr.pop()
                if xx == x:
                    continue
                
                xx = x
                ss = s + x
                
                d.add(-ss)
                
                if n and r1(ss, list(arr), n-1):
                    return True

        # print(a)
        if r1(0, a, len(a) // 2):
            return True
        # print(d)
        # print(b)
        
        def r2(s, arr, n):
            xx = None
            while arr:
                x = arr.pop()
                if xx == x:
                    continue
                
                xx = x
                ss = s + x
                if ss in d:
                    return True
                
                if n and r2(ss, list(arr), n-1):
                    return True
        if r2(0, b, len(b) // 2 - 1):
            return True
        # print(d)
        return False


            


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        su = sum(A)
        ii = len(A)//2+1
        arr = [set() for _ in range(ii)]
        arr[0].add(0)
        for x in A:
            for t in reversed(range(1,ii)):
                arr[t]|=set(map(lambda s:s+x,arr[t-1]))
        # print(arr)
        for i in range(1,len(A)//2+1):
            if (su*i)%len(A)==0:
                # print(i, su*i, arr[i])
                if (su*i)//len(A) in arr[i]:
                    return True
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        from fractions import Fraction
        N = len(A)
        S = sum(A)
        A = [z - Fraction(S, N) for z in A]
        
        if N == 1:
            return False
        
        left = {A[0]}
        
        for i in range(1, N//2):
            left = {z + A[i] for z in left} | left | {A[i]}
        
        if 0 in left:
            return True
        
        right = {A[-1]}
        
        for i in range(N//2, N-1):
            right = {z + A[i] for z in right} | right |{A[i]}
        
        if 0 in right:
            return True
        
        sleft = sum(A[i] for i in range(N//2))
        sright = sum(A[i] for i in range(N//2, N))
        
        return any(-ha in right and (ha, -ha) != (sleft, sright) for ha in left)
            


class Solution(object):
    def splitArraySameAverage(self, A):
        from fractions import Fraction
        N = len(A)
        S = sum(A)
        A = [z - Fraction(S, N) for z in A]

        if N == 1: return False

        #Want zero subset sum
        left = {A[0]}
        for i in range(1, N//2):
            left = {z + A[i] for z in left} | left | {A[i]}
        if 0 in left: return True

        right = {A[-1]}
        for i in range(N//2, N-1):
            right = {z + A[i] for z in right} | right | {A[i]}
        if 0 in right: return True

        sleft = sum(A[i] for i in range(N//2))
        sright = sum(A[i] for i in range(N//2, N))

        return any(-ha in right and (ha, -ha) != (sleft, sright) for ha in left)

class Solution(object):
    def splitArraySameAverage(self, A):
        from fractions import Fraction
        N = len(A)
        S = sum(A)
        A = [z - Fraction(S, N) for z in A]

        if N == 1: return False

        #Want zero subset sum
        left = {A[0]}
        for i in range(1, int(N/2)):
            left = {z + A[i] for z in left} | left | {A[i]}
        if 0 in left: return True

        right = {A[-1]}
        for i in range(int(N/2), N-1):
            right = {z + A[i] for z in right} | right | {A[i]}
        if 0 in right: return True

        sleft = sum(A[i] for i in range(int(N/2)))
        sright = sum(A[i] for i in range(int(N/2), N))

        return any(-ha in right and (ha, -ha) != (sleft, sright) for ha in left)

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        ksums = [{0}]
        maxk = len(A) // 2
        
        n = len(A)
        S = sum(A)
        for a in A:
            #print('a', a)
            #print('ksums', ksums)
            nksums = [[0]]
            for k in range(1, min(len(ksums), maxk) + 1):
                row = (ksums[k] if k < len(ksums) else set()) | {a + x for x in ksums[k - 1]}
                if any(x * (n - k) == k * (S - x) for x in row):
                    return True
            
                nksums.append(row)
                
            ksums = nksums
            #print('ksums*', ksums)
            
        
        return False

from fractions import Fraction
class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        N = len(A)
        S = sum(A)
        A = [z - Fraction(S, N) for z in A]

        if N == 1: return False

        #Want zero subset sum
        left = {A[0]}
        for i in range(1, N//2):
            left = {z + A[i] for z in left} | left | {A[i]}
        if 0 in left: return True

        right = {A[-1]}
        for i in range(N//2, N-1):
            right = {z + A[i] for z in right} | right | {A[i]}
        if 0 in right: return True

        sleft = sum(A[i] for i in range(N//2))
        sright = sum(A[i] for i in range(N//2, N))

        return any(-ha in right and (ha, -ha) != (sleft, sright) for ha in left)

#
# @lc app=leetcode id=805 lang=python3
#
# [805] Split Array With Same Average
#
# https://leetcode.com/problems/split-array-with-same-average/description/
#
# algorithms
# Hard (24.71%)
# Likes:    244
# Dislikes: 49
# Total Accepted:    10.3K
# Total Submissions: 41.6K
# Testcase Example:  '[1,2,3,4,5,6,7,8]'
#
# 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 fractions import Fraction

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        # Time  complexity: O(2^(N/2))
        # Space complexity: O(2^(N/2))
        N, S = len(A), sum(A)
        A = [z - Fraction(S, N) for z in A]

        if N == 1: return False

        left = {A[0]}
        for i in range(1, N//2):
            left = {z + A[i] for z in left} | left | {A[i]}
        if 0 in left: return True

        right = {A[-1]}
        for i in range(N//2, N-1):
            right = {z + A[i] for z in right} | right | {A[i]}
        if 0 in right: return True

        sleft = sum(A[i] for i in range(N//2))
        sright = sum(A[i] for i in range(N//2, N))

        return any(-ha in right and (ha, -ha) != (sleft, sright) for ha in left)

        


        



class Solution1:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        
        N = len(A)
        
        if N <= 1:
            return False
        
        max_sum = sum(A)
        #print(max_sum)
        sums = [0] * (max_sum+1)
        for i in range(N):
            num = A[i]
            for s in range(max_sum, num-1, -1):
                if sums[s-num]:
                    sums[s] |= sums[s-num] << 1
            sums[num] |= 1
            #print(sums)
        #print(sums)
        for l in range(1, N):
            if (max_sum * l) % N == 0:
                s = int((max_sum * l) / N)
                if (sums[s] >> (l-1)) & 1:
                    return True
        return False

import math
class Solution2:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        A.sort(reverse=True)
        N = len(A)
        if N <= 1:
            return False
        max_size = math.ceil(N / 2)
        
        max_sum = sum(A)
        target_mean = max_sum / N
        #print(target_mean)
        ans = False
        
        def choose(max_n, curr_n, curr_sum, next_id):
            nonlocal target_mean
            nonlocal ans
            nonlocal N
            #print(max_n, curr_n, curr_sum, next_id)
            if ans:
                return
            if curr_n > max_n:
                return
            if curr_n:
                curr_mean = curr_sum / curr_n
                if curr_mean < target_mean:
                    return
                if curr_mean == target_mean:
                    ans = True
                    return
            if next_id == N -1:
                return
            for i in range(next_id, N):
                choose(max_n, curr_n + 1, curr_sum + A[i], i+1)
        
        choose(max_size, 0, 0, 0)
        
        return ans
    
class Solution(object):
    def splitArraySameAverage(self, A):
        from fractions import Fraction
        N = len(A)
        S = sum(A)
        A = [z - Fraction(S, N) for z in A]

        if N == 1: return False

        #Want zero subset sum
        left = {A[0]}
        for i in range(1, N//2):
            left = {z + A[i] for z in left} | left | {A[i]}
        if 0 in left: return True

        right = {A[-1]}
        for i in range(N//2, N-1):
            right = {z + A[i] for z in right} | right | {A[i]}
        if 0 in right: return True

        sleft = sum(A[i] for i in range(N//2))
        sright = sum(A[i] for i in range(N//2, N))

        return any(-ha in right and (ha, -ha) != (sleft, sright) for ha in left)

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        tot = sum(A)
        n = len(A)
        target = tot/n 
        visited = [ False]*len(A)
        m = n // 2
        possible = False
        for i in range(1, m+ 1):
            if (tot * i)%n == 0:
                possible = True
                break
        if not possible:
            return False
        A.sort( )
        
        
        def helper(A, cursum, curcnt, pos):
            if curcnt == 0:
                return cursum == 0
            if A[pos] >cursum/curcnt:
                return False
            for i in range(pos, len(A) - curcnt + 1):
                if i > pos and A[i]==A[i-1]:
                    continue
                if helper(A, cursum - A[i], curcnt - 1, i + 1):
                    return True
            
            return False
         
        for i in range(1, m + 1):
            if (tot * i)%n == 0 and helper(A, (tot * i)/n, i, 0):
                return True
        return False
            
            


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        dp = set([(0,0)])
        suma = sum(A)
        N = len(A)
        A.sort()
        for num in A:
            for k, v in list(dp):
                if k>=N//2: continue
                if num+v>suma*(k+1)//N: continue
                # print(k, v, num, dp)    
                if num+v==suma*(k+1)//N and suma*(k+1)%N==0 and k+1<N:
                    return True

                dp.add((k+1, num+v))
        
        return False



class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        total = sum(A)
        sets = [{0}] + [set() for _ in A]
        for num in A:
            for j in reversed(list(range(len(A) - 1))):
                for k in sets[j]:
                    s = k + num
                    if total * (j + 1) == s * len(A):
                        return True
                    sets[j + 1].add(k + num)
        
        return False


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        total = sum(A)
        l = len(A)
        dp = [0] * (total + 1)
        dp[A[0]] = 2
        for i in range(1, l):
            for j in range(total - A[i], -1, -1):
                dp[j + A[i]] |= (dp[j] << 1)
            dp[A[i]] |= 2
        
        for i in range(1, l):
            if (total * i) % l == 0 and ((1 << i) & dp[total * i // l]) > 0:
                return True
        return False


from fractions import Fraction
class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        if len(A) == 1: return False
        avg = Fraction(sum(A), len(A))
        A = [num - avg for num in A]
        left = set()
        for i in range(len(A) // 2):
            curr_set = {s + A[i] for s in left}
            left = left | curr_set | {A[i]}
        if 0 in left: return True
        rsum = sum(A[i] for i in range(len(A) // 2, len(A)))
        right = set()
        for i in range(len(A) // 2, len(A)):
            if A[i] == 0: return True
            curr_set = {A[i]}
            for s in right:
                if s + A[i] == 0 or (- s - A[i] in left and s + A[i] != rsum):
                    return True
                curr_set.add(s + A[i])
            right = right | curr_set
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        avg, N = sum(A), len(A)
        if N < 2: return False
        if N == 2: return A[0] == A[1]
        A = [num*N - avg for num in A]
        
        dp = collections.defaultdict(set)
        # Last element goes to another array
        for i, n in enumerate(A[:-1]):
            if n == 0: return True # Single element array
            if i == 0:
                dp[0].add(n)
                continue
            sums = set()
            sums.add(n)
            for j, s in dp.items():
                for ps in s:
                    if ps + n == 0:
                        return True
                    sums.add(ps+n)
            dp[i] = sums
        return False

class Solution:
    def splitArraySameAverage(self, A) -> bool:
        if sum(A)==0 and len(A)>1:
            return True
        elif len(A)==1:
            return False
        mem={}
        ss=sum(A)
        n=len(A)
        def rec(index,cur_sum,length):
            if cur_sum*(n-length)==length*(ss-cur_sum) and length>0 and length<n:
                return True
            elif index==n:
                return False
            elif (index,cur_sum) in mem:
                return mem[(index,cur_sum)]
            else:
                mem[(index,cur_sum)]=(rec(index+1,cur_sum+A[index],length+1) | rec(index+1,cur_sum,length))
                return mem[(index,cur_sum)]
            
        return rec(0,0,0)

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:

        if len(A) < 3:
            return False
        
        sumA, lenA = sum(A), len(A)
        
        if sumA / lenA in A:
            return True
        
        A = [i * lenA - sumA for i in A]
        A.sort()
        
        a = [i for i in A if i < 0]
        b = [i for i in A if i > 0]
        
        if len(a) > len(b):
            a, b = b, a
        
        # d = {-i for i in a}
        d = set()
        def r1(s, arr, n):
            xx = None
            while arr:
                x = arr.pop()
                if xx == x:
                    continue
                
                xx = x
                ss = s + x
                
                d.add(-ss)
                
                if n and r1(ss, list(arr), n-1):
                    return True

        # print(a)
        if r1(0, a, len(a) // 2):
            return True
        # print(d)
        # print(b)
        
        def r2(s, arr, n):
            xx = None
            while arr:
                x = arr.pop()
                if xx == x:
                    continue
                
                xx = x
                ss = s + x
                if ss in d:
                    return True
                
                if n and r2(ss, list(arr), n-1):
                    return True
        if r2(0, b, len(b) // 2 - 1):
            return True
        # print(d)
        return False


            


class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        S = sum(A)
        L = len(A)
        if L == 1: return False
        sizes = {(0,0)}
        for n in A:
            for s,c in sizes.copy():
                if c<L//2:
                    sizes.add((s+n,c+1))
        sizes.remove((0,0))
        for s,c in sizes:
            if s*(L-c) == (S-s)*c:
                return True
        return False

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        
        N = len(A)
        
        if N <= 1:
            return False
        
        max_sum = sum(A)
        print(max_sum)
        sums = [0] * (max_sum+1)
        for i in range(N):
            num = A[i]
            for s in range(max_sum, num-1, -1):
                if sums[s-num]:
                    sums[s] |= sums[s-num] << 1
            sums[num] |= 1
            #print(sums)
        #print(sums)
        for s in range(max_sum+1):
            for i in range(N-1):
                if (sums[s] >> i) & 1:
                    mean = s / (i + 1)
                    rem = (max_sum - s) / (N - (i + 1))
                    if mean == rem:
                        return True
                    
        return False           

class Solution:
    dp = []
    def is_possible(self, l, actual_sum, index, curr_sum, curr_element_count):
        if index >= len(l):
            return False
        if Solution.dp[curr_element_count][curr_sum] != None:
            return Solution.dp[curr_element_count][curr_sum]
        if curr_element_count!=0 and (actual_sum-curr_sum) / (len(l)-curr_element_count) == curr_sum/curr_element_count:
            print(curr_sum/curr_element_count)
            return True
        Solution.dp[curr_element_count][curr_sum] =  self.is_possible(
            l, actual_sum, index+1, curr_sum+l[index], curr_element_count+1
            ) or self.is_possible(
                l, actual_sum, index+1, curr_sum, curr_element_count
                )
        return Solution.dp[curr_element_count][curr_sum]

    def splitArraySameAverage(self, A: List[int]) -> bool:
        if A == None or len(A) <=1:
            return False
        Solution.dp = [[None] * (sum(A)+10) for _ in range(len(A)+1)]
        return self.is_possible(A, sum(A), 0, 0, 0)

class Solution:
    dp = []
    def is_possible(self, l, actual_sum, index, curr_sum, curr_element_count):
        if index >= len(l):
            return False
        if Solution.dp[curr_element_count][curr_sum] != None:
            return Solution.dp[curr_element_count][curr_sum]
        if curr_element_count!=0 and (actual_sum-curr_sum) / (len(l)-curr_element_count) == curr_sum/curr_element_count:
            #print(curr_sum/curr_element_count)
            return True
        Solution.dp[curr_element_count][curr_sum] =  self.is_possible(
            l, actual_sum, index+1, curr_sum+l[index], curr_element_count+1
            ) or self.is_possible(
                l, actual_sum, index+1, curr_sum, curr_element_count
                )
        return Solution.dp[curr_element_count][curr_sum]

    def splitArraySameAverage(self, A: List[int]) -> bool:
        if A == None or len(A) <=1:
            return False
        Solution.dp = [[None] * (sum(A)+10) for _ in range(len(A)+1)]
        return self.is_possible(A, sum(A), 0, 0, 0)

class Solution:
    def splitArraySameAverage(self, A: List[int]) -> bool:
        # A = [53,6,3,34,91,82,47,9,70,1]
        if len(A) < 3:
            return False
        
        sumA, lenA = sum(A), len(A)
        
        if sumA / lenA in A:
            return True
        
        A = [i * lenA - sumA for i in A]
        A.sort()
        
        a = [i for i in A if i < 0]
        b = [i for i in A if i > 0]
        
        if len(a) > len(b):
            a, b = b, a
        
        d = {-i for i in A}
        def r(s, arr, n):
            xx = None
            while arr:
                x = arr.pop()
                if xx == x:
                    continue
                
                xx = x
                ss = s + x
                if ss in d:
                    return True
                
                d.add(-ss)
                
                if n and r(ss, list(arr), n-1):
                    return True

        # print(a)
        if r(0, a, len(a) - 1):
            return True
        # print(d)
        # print(b)
        if r(0, b, len(b) // 2 - 1):
            return True
        # print(d)
        return False