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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Bit manipulation

Data structures

Mathematics

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:
		(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)
		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:

		@lru_cache(None)
		def find(target, k, i):
			if k == 0:
				return target == 0
			if k + i > len(A):
				return False
			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))


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:
		A.sort(reverse=True)

		def helper(goal, cnt):

			@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):
			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:
		(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):
			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):
			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:
		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:
		memo = {}

		def dfs(idx, k, total) -> bool:
			if k == 0:
				return total == 0
			if k + idx > len(A):
				return False
			if (idx, k, total) in memo:
				return memo[idx, k, total]
			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))
		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:
		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:
						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:
		A.sort()
		DP = [set() for _ in range(len(A) // 2 + 1)]
		all_sum = sum(A)
		DP[0] = set([0])
		for item in A:
			for count in range(len(DP) - 2, -1, -1):
				if len(DP[count]) > 0:
					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


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


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:
		ksums = [{0}]
		maxk = len(A) // 2
		for a in A:
			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)]
		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:
		N = len(A)
		if N <= 1:
			return False
		max_sum = sum(A)
		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
		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:
		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:
		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:
		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]))
		for i in range(1, len(A) // 2 + 1):
			if su * i % len(A) == 0:
				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 Solution1:

	def splitArraySameAverage(self, A: List[int]) -> bool:
		N = len(A)
		if N <= 1:
			return False
		max_sum = sum(A)
		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
		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
		ans = False

		def choose(max_n, curr_n, curr_sum, next_id):
			nonlocal target_mean
			nonlocal ans
			nonlocal N
			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
		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:
		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
				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)
		for (i, n) in enumerate(A[:-1]):
			if n == 0:
				return True
			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:
		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:
	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:
		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
		if r(0, a, len(a) - 1):
			return True
		if r(0, b, len(b) // 2 - 1):
			return True
		return False