1
class Solution:
2
    def splitArraySameAverage(self, A: List[int]) -> bool:
3
        A.sort()
4
        DP = [
5
            set() for _ in range(len(A) // 2 + 1)
6
        ]  # DP[i] stores the all available sum with i items in a bracket
7
        all_sum = sum(A)
8
        DP[0] = set([0])
9
        for item in A:  # iterate over items in the list
10
            for count in range(
11
                len(DP) - 2, -1, -1
12
            ):  # iterate backwards w.r.t. the bracket size
13
                if (
14
                    len(DP[count]) > 0
15
                ):  # if DP[i] is not empty, then update DP[i+1] by adding the current item into all sums in DP[i]
16
                    for a in DP[count]:
17
                        DP[count + 1].add(a + item)
18
        for size in range(1, len(DP)):
19
            if all_sum * size / len(A) in DP[size]:
20
                return True
21
        return False