/ ALGORITHM

LeetCode Weekly Contest 77

Contest Information

source: It’s from the LeetCode

Description

对于一个数组 $A$, 请问是否能将它拆分成两个非空且平均数相等的数组 $B$ 和 $C$

数据范围:$ 1 ≤ len(A) ≤ 30; 0 ≤ A[i] ≤ 10000 $

Input

[1,2,3,4,5,6,7,8]                                                                  

Output

true                                                                               

Solution 1

首先,容易得出 $B, C$ 的平均数和 $A$ 一样,所以平均数是已知的;那么,问题转换成求 $A$ 的一个真子集且平均数为 $average(A)$。
如果选择直接枚举 $A$ 中的元素,那可能性有 $2^{len(A)}$ 种,不可行;所以我们可以用分治的方法:将 $A$ 拆分成两半,先在每一边中查找是否存在解,再判断它们合并是否存在解。复杂度为 $O(2^{len(A)/2})$,可以接受。

AC code

from fractions import Fraction                                                     
class Solution:
    def splitArraySameAverage(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        N = len(A)
        if N == 1: return False
        S = sum(A)
        A = [x - Fraction(S, N) for x in A]
        
        left = {A[0]}
        for i in range(1, int(N/2)):
            left = { x + A[i] for x in left} | left | {A[i]}
            if 0 in left: return True
        
        right = {A[-1]}
        for i in range(int(N/2), N-1):
            right = { x + A[i] for x in right } | right | {A[i]}
            if 0 in right: return True
            
        sum_left = sum(A[i] for i in range(int(N/2)))
        sum_right = sum(A[i] for i in range(int(N/2), N))
        
        return any(-dis in right and (dis, -dis) != (sum_left, sum_right) for dis in left)

Solution 2

如果存在这么一个满足条件的子集 $B$,那么必定有 $\frac{sum(B)}{len(B)} = \frac{sum(A)}{len(A)}$,所以我们可以以此为判断条件来查找是否有解。
设 $DP[s][n]$ 为是否存在长度为 $n$,且和为 $s$ 的子集,可以在 $O((len(A))^2\times sum(A))$ 的复杂度下求解。

AC code

class Solution {                                                                         
public:
    bool splitArraySameAverage(vector<int>& A) {
        int sum = 0, len = A.size();
        for(int i=0; i<len; i++) sum+=A[i];
        vector<vector <bool> > DP(sum+1 ,vector<bool>(len+1,0));   
        DP[0][0] = true;
        for(int i=0; i<len; i++)
        {
            for(int s=sum; s>=A[i]; s--)
            {
                for(int n=1; n<=i+1; n++)
                {
                    DP[s][n] = DP[s][n] | DP[s-A[i]][n-1];
                }
            }
        }
        for (int i = 1; i < len; i++) {
            int cnt = sum * i;
            if ( cnt%len == 0) {
                if (DP[cnt/len][i]) return true;
            }
        }
        return false;
    }
};