805. 数组的均值分割

805. 数组的均值分割

高度相似题：1755. 最接近目标值的子序列和，1755简单一点，我是看了1755才会的805

一个比较重要的处理是把求平均值，转化成求选择子集和等于0（该子集不为全也不为空）。

为啥可以直接把lsum和rsum的头和尾pop掉：

• 如果left全不选，那就等同于只从right中选，前面已经遍历过了。
• 如果left全选，那就从right中选出子集mask，使得lsum.back()+right[mask]==0。如果这样的话，因为总和sum是0，也就相当于left全不选，从right中选择剩余子集
  (1<<n2)-1-mask使得和为0，也就是直接变成了求right[((1<<n2)-1)^mask]，前面的只从right中选已经遍历过了。

所以这两种情况都没有了，可以直接把lsum和rsum的头和尾pop掉。

class Solution {
 public:
  int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
  bool splitArraySameAverage(vector<int>& nums) {
    int sum = 0, cnt = nums.size(), n = nums.size();
    if (n == 1) return false;
    for (auto i : nums) sum += i;
    cnt /= gcd(sum, n);
    sum /= gcd(sum, n);

    for (auto& i : nums) i = i * cnt - sum;
    int n1 = n / 2, n2 = n - n / 2;
    vector<int> lsum(1 << n1), rsum(1 << n2);
    for (int i = 0; i < 1 << n1; i++)
      for (int j = 0; j < n1; j++)
        if (i & (1 << j)) lsum[i] = lsum[i ^ (1 << j)] + nums[j];
    for (int i = 0; i < 1 << n2; i++)
      for (int j = 0; j < n2; j++)
        if (i & (1 << j)) rsum[i] = rsum[i ^ (1 << j)] + nums[n1 + j];

    for (int i = 1; i < lsum.size(); i++)
      if (!lsum[i]) return true;
    for (int i = 1; i < rsum.size(); i++)
      if (!rsum[i]) return true;

    lsum.pop_back(), rsum.pop_back();
    lsum.erase(lsum.begin());
    rsum.erase(rsum.begin());

    sort(lsum.begin(), lsum.end());
    sort(rsum.begin(), rsum.end());

    int i = 0, j = rsum.size() - 1;
    while (i < lsum.size() && j >= 0) {
      int s = lsum[i] + rsum[j];
      if (s > 0)
        j--;
      else if (s < 0)
        i++;
      else
        return true;
    }
    return false;
  }
};