Участник:Alexander Denisenko/split array same average

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution(object):
    def splitArraySameAverage(self, A):
        N = len(A)
        mean = sum(A)
 
        if N < 2: 
            return False
        if N == 2: 
            return A[0] == A[1]
 
        A = [num * N - mean 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