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

sum / n = sum1 / k = sum2 / (n - k)

``````class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int n = A.size(), m = n / 2, sum = accumulate(A.begin(), A.end(), 0);
bool possible = false;
for (int i = 1; i <= m && !possible; ++i) {
if (sum * i % n == 0) possible = true;
}
if (!possible) return false;
vector<unordered_set<int>> dp(m + 1);
dp[0].insert(0);
for (int num : A) {
for (int i = m; i >= 1; --i) {
for (auto a : dp[i - 1]) {
dp[i].insert(a + num);
}
}
}
for (int i = 1; i <= m; ++i) {
if (sum * i % n == 0 && dp[i].count(sum * i / n)) return true;
}
return false;
}
};
``````

``````class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int n = A.size(), m = n / 2, sum = accumulate(A.begin(), A.end(), 0);
bool possible = false;
for (int i = 1; i <= m && !possible; ++i) {
if (sum * i % n == 0) possible = true;
}
if (!possible) return false;
bitset<300001> bits[m + 1] = {1};
for (int num : A) {
for (int i = m; i >= 1; --i) {
bits[i] |= bits[i - 1] << num;
}
}
for (int i = 1; i <= m; ++i) {
if (sum * i % n == 0 && bits[i][sum * i / n]) return true;
}
return false;
}
};
``````

``````class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int n = A.size(), m = n / 2, sum = accumulate(A.begin(), A.end(), 0);
bool possible = false;
for (int i = 1; i <= m && !possible; ++i) {
if (sum * i % n == 0) possible = true;
}
if (!possible) return false;
sort(A.begin(), A.end());
for (int i = 1; i <= m; ++i) {
if (sum * i % n == 0 && helper(A, sum * i / n, i, 0)) return true;
}
return false;
}
bool helper(vector<int>& A, int curSum, int curNum, int start) {
if (curNum == 0) return curSum == 0;
if (A[start] > curSum / curNum) return false;
for (int i = start; i < A.size() - curNum + 1; ++i) {
if (i > start && A[i] == A[i - 1]) continue;
if(helper(A, curSum - A[i], curNum - 1, i + 1)) return true;
}
return false;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/805

Combination Sum III

Partition Equal Subset Sum

https://leetcode.com/problems/split-array-with-same-average/

https://leetcode.com/problems/split-array-with-same-average/discuss/120660/Java-accepted-recursive-solution-with-explanation

https://leetcode.com/problems/split-array-with-same-average/discuss/120842/DP-with-bitset-over-*sum*-(fast-PythonRuby-decent-C%2B%2B)

https://leetcode.com/problems/split-array-with-same-average/discuss/120667/C%2B%2B-Solution-with-explanation-early-termination-(Updated-for-new-test-case)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation