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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

class Solution { public: bool splitArraySameAverage(vector<int> &A) { int sz = A.size(); int szb = sz / 2; //size of the smaller array int sum = 0; for (auto n : A) sum += n; bool possible = false; for (int k = 1; k <= szb; ++k) { if (sum * k % sz == 0) { possible = true; break; } } if (!possible) return false; vector<unordered_set<int>> dp(szb+1); dp[0].insert(0); for(int i=0; i<sz; ++i){ vector<unordered_set<int>> dp0 = dp; for(int j=1; j<=min(szb,i+1); ++j){ for(auto s:dp0[j-1]){ dp[j].insert(s+A[i]); } } } for(int k=1; k<=szb; ++k){ if(sum*k%sz==0 && dp[k].count(sum*k/sz)!=0) return true; } return false; } };