【动态规划】【数学】【C++算法】805 数组的均值分割

int GCD(int n1, int n2)
{
  int t1 = min(n1, n2);
  int t2 = max(n1, n2);
  if (0 == t1)
  {
    return t2;
  }
  return GCD(t2 % t1, t1);
}
class Solution {
public:
  bool splitArraySameAverage(vector<int>& nums) {
    const int n = nums.size();
    const int half = n / 2;
    vector<unordered_set<int>> vLeft(1), vRight(1);   
    CountToTotal( vLeft, nums.data(),0, half);
    CountToTotal(vRight, nums.data()+half, 0, n-half);
    const int total = std::accumulate(nums.begin(), nums.end(),0);
    for (int i = 1; i <= half; i++)
    {
      const int iGCD = GCD(i, n);
      if (0 != total % (n / iGCD))
      {
        continue;//A的和必定为整数
      }
      const int totalA = total * i / n;
      for (int j = 0; j <= i; j++)
      {// A数组总共选择i个，其中从左边选择j个
        for (const auto& iLeft : vLeft[j])
        {
          if (vRight[i - j].count(totalA - iLeft))
          {
            return true;
          }
        }
      }
    }
    return false;
  }
  void CountToTotal(std::vector<std::unordered_set<int>>& v, const int* p,int left,int r)
  {
    v[0].emplace(0);
    for (int i = left; i < r ; i++)
    {
      v.emplace_back();
      for (int j = v.size() - 1; j >= 1; j--)
      {
        for (const auto& pre : v[j - 1])
        {
          v[j].emplace(pre + p[i]);
        }
      }
    }
  }
};

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vector<int> nums;
  {
    Solution sln;
    nums = { 1,2,3,4,5,6,7,8 };
    auto res = sln.splitArraySameAverage(nums);
    Assert(true, res);
  }
  {
    Solution sln;
    nums = { 3,1};
    auto res = sln.splitArraySameAverage(nums);
    Assert(false, res);
  }
  {
    Solution sln;
    nums = { 18,10,5,3 };
    auto res = sln.splitArraySameAverage(nums);
    Assert(false, res);
  }
}