805. Split Array With Same Average

805. Split Array With Same Average

Topic: pruning  + DP.

Copmplexity: O(n^3).

Soltion:

 Code:

class Solution {
public:
    bool is_possible(int m, int sum, int n)
{
  bool possible = false;
  for(int i = 1; i <= m; i++)
    if(sum*i % n == 0)possible = true;

  return possible;
}

bool splitArraySameAverage (const vector<int>& A)
{
  int n = A.size();
  int m = n/2;

  int sum = accumulate(A.begin(), A.end(), 0);

  if(!is_possible(m,sum,n)) return false;///pruning

  vector<unordered_set<int> > ans(m+1);

  ans[0].insert(0);

  for(int num : A)
    for(int i = m; i >= 1; i--)
      for(int t : ans[i-1])
        ans[i].insert(t+num);

  for(int i = 1; i <= m; i++){
    if(sum*i %n == 0 && ans[i].find(sum*i/n) != ans[i].end())return true;
  }
  return false;

/**

sums[0].insert (0);

for (int num : A)

for (int i = m; i >= 1; --i)

transform (sums[i - 1].begin (), sums[i - 1].end (),

inserter (sums[i], sums[i].end ()),

[num](int t) { return t + num; });

for (int i = 1; i <= m; ++i)

if (sum * i % n == 0 && sums[i].count (sum * i / n)) return true;

return false;
**/

vector<unordered_set<int>> sums (m + 1);

}
};

Share: