# [LeetCode] 805. Split Array With Same Average 用相同均值拆分数组

2021年09月15日 阅读数：1

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.)html

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

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

The key thing of this problem is, when we are able to make a same average split, the average of each splitted array is the same as the average of the whole array.
So the problem can be transformed into a simpler one: given a target number (tosum), can we construct it using a specific number (lenB) of integers in a list(A).
Then we can try every possible numbers of lenB, to see whether any one is feasible.post

If the array of size n can be splitted into group A and B with same mean, assuming A is the smaller group, thenthis

totalSum/n = Asum/k = Bsum/(n-k), where k = A.size() and 1 <= k <= n/2;
Asum = totalSum*k/n, which is an integer. So we have totalSum*k%n == 0;url

If there are still some k valid after early pruning by checking totalSum*k%n == 0,
we can generate all possible combination sum of k numbers from the array using DP, like knapsack problem. (Note: 1 <= k <= n/2)
Next, for each valid k, simply check whether the group sum, i.e. totalSum * k / n, exists in the kth combination sum hashset.

vector<vector<unordered_set<int>>> sums(n, vector<unordered_set<int>>(n/2+1));
sums[i][j] is all possible combination sum of j numbers from the subarray A[0, i];
Goal: sums[n-1][k], for all k in range [1, n/2]
Initial condition: sums[i][0] = {0}, 0 <= i <= n-1; sums[0][1] = {all numbers in the array};
Deduction: sums[i+1][j] = sums[i][j] "join" (sums[i][j-1] + A[i+1])
The following code uses less space but the same DP formula.
Runtime analysis:
All numbers in the array are in range [0, 10000]. Let M = 10000.
So the size of kth combination sum hashset, i.e. sums[...][k], is <= k * M;
For each number in the array, the code need loop through all combination sum hashsets, so
the total runtime is n * (1 * M + 2 * M + ... + (n/2) * M) = O(n^3 * M)

Python:

```class Solution(object):
def splitArraySameAverage(self, A):
if len(A)==1: return False
global_avg = sum(A)/float(len(A))
for lenB in range(1, len(A)/2+1):
if int(lenB*global_avg) == lenB*global_avg:
if self.exist(lenB*global_avg, lenB, A):
return True
return False

def exist(self, tosum, item_count, arr):
if item_count==0:
return False if tosum else True
if item_count > len(arr) or not arr:
return False
if any([self.exist(tosum-arr[0], item_count-1, arr[1:]),
self.exist(tosum, item_count, arr[1:])]):
return True
return False　```

Python:

```# Time:  O(n^4)
# Space: O(n^3)
class Solution(object):
def splitArraySameAverage(self, A):
"""
:type A: List[int]
:rtype: bool
"""
def possible(total, n):
for i in xrange(1, n//2+1):
if total*i%n == 0:
return True
return False
n, s = len(A), sum(A)
if not possible(n, s):
return False

sums = [set() for _ in xrange(n//2+1)];
for num in A:  # O(n) times
for i in reversed(xrange(1, n//2+1)):  # O(n) times
for prev in sums[i-1]:  # O(1) + O(2) + ... O(n/2) = O(n^2) times
for i in xrange(1, n//2+1):
if s*i%n == 0 and s*i//n in sums[i]:
return True
return False　　```

C++: 1

```class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int n = A.size(), m = n/2, totalSum = accumulate(A.begin(), A.end(), 0);
// early pruning
bool isPossible = false;
for (int i = 1; i <= m && !isPossible; ++i)
if (totalSum*i%n == 0) isPossible = true;
if (!isPossible) return false;
// DP like knapsack
vector<unordered_set<int>> sums(m+1);
sums[0].insert(0);
for (int num: A) {
for (int i = m; i >= 1; --i)
for (const int t: sums[i-1])
sums[i].insert(t + num);
}
for (int i = 1; i <= m; ++i)
if (totalSum*i%n == 0 && sums[i].find(totalSum*i/n) != sums[i].end()) return true;
return false;
}
};　　```

C++: 1

```class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int n = A.size(), m = n / 2;
int totalSum = accumulate(A.begin(), A.end(), 0);
// early pruning
bool isPossible = false;
for (int i = 1; i <= m; ++i) {
if (totalSum * i % n == 0) {
isPossible = true;
break;
}
}
if (!isPossible) {
return false;
}
// DP like knapsack
vector<unordered_set<int>> sums(m + 1);
sums[0].insert(0);
for (int num: A) {  // for each element in A, we try to add it to sums[i] by joining sums[i - 1]
for (int i = m; i >= 1; --i) {
for (const int t: sums[i - 1]) {
sums[i].insert(t + num);
}
}
}
for (int i = 1; i <= m; ++i) {
if (totalSum * i % n == 0 && sums[i].find(totalSum * i / n) != sums[i].end()) {
return true;
}
}
return false;
}
};　　```

C++: 2 TLE

```class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int n = A.size(), m = n/2, totalSum = accumulate(A.begin(), A.end(), 0);
sort(A.rbegin(), A.rend()); // Optimization
for (int i = 1; i <= m; ++i)
if (totalSum*i%n == 0 && combinationSum(A, 0, i, totalSum*i/n)) return true;
return false;
}
bool combinationSum(vector<int>& nums, int idx, int k, int tar) {
if (tar > k * nums[idx]) return false; // Optimization, A is sorted from large to small
if (k == 0) return tar == 0;
for (int i = idx; i <= nums.size()-k; ++i)
if (nums[i] <= tar && combinationSum(nums, i+1, k-1, tar-nums[i])) return true;
return false;
}
};
```