805. Split Array With Same Average

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

直接DFS会超时，因为最后average相等，其实满足条件的average是有限的，先求出可能的值在dfs

class Solution:
    def splitArraySameAverage(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        s = sum(A)
        ave = s/len(A)
        res = []
        for i in range(1, len(A)//2+1):
            s1=ave*i
            if s1-int(s1)<0.0000001:
                res.append([i,int(s1)])
                
        def dfs(i,cnt,t):
            if cnt==0 and t==0: return True
            if cnt==0 or t<0: return False
            if i==len(A): return False
            if dfs(i+1, cnt, t): return True
            if dfs(i+1, cnt-1, t-A[i]): return True
        
        for c, s in res:
            if dfs(0, c, s): return True   
        return False
        
s=Solution()
print(s.splitArraySameAverage([1,2,3,4,5,6,7,8]))