1
class Solution {
2
 public:
3
  int totsum;
4
  bool findans(vector<set<int>> &dp, vector<int> &nums, int start, int sum, int bitcnt) {
5
    if (start == nums.size()) {
6
      for (int i = 0; i < dp.size(); i++)
7
        if (i + bitcnt != 0 && i + bitcnt != nums.size() &&
8
            ((i + bitcnt) * totsum) % nums.size() == 0 &&
9
            dp[i].find((((i + bitcnt) * totsum) / nums.size()) - sum) != dp[i].end())
10
          return true;
11
      return false;
12
    }
13
    return findans(dp, nums, start + 1, sum, bitcnt) ||
14
           findans(dp, nums, start + 1, sum + nums[start], bitcnt + 1);
15
  }
16

17
  void filldp(vector<set<int>> &dp, vector<int> &nums, int start, int mask) {
18
    if (start == nums.size() / 2) {
19
      int sum = 0, cnt = 0;
20
      for (int i = 0; i < nums.size(); i++)
21
        if (mask & (1 << i)) {
22
          sum += nums[i];
23
          cnt++;
24
        }
25
      dp[cnt].insert(sum);
26
      return;
27
    }
28
    filldp(dp, nums, start + 1, mask);
29
    filldp(dp, nums, start + 1, mask ^ (1 << start));
30
  }
31

32
  bool splitArraySameAverage(vector<int> &nums) {
33
    totsum = 0;
34
    for (int i = 0; i < nums.size(); i++) totsum += nums[i];
35
    vector<set<int>> dp(nums.size() / 2 + 1);
36
    filldp(dp, nums, 0, 0);
37
    return findans(dp, nums, nums.size() / 2, 0, 0);
38
  }
39
};