Untitled
unknown
c_cpp
2 years ago
987 B
7
Indexable
class Solution { public: bool splitArraySameAverage(vector<int>& nums) { int n = nums.size(); if (n <= 1) return false; if (n == 2) return (nums[0] == nums[1]); int total = 0; for (int e: nums) total += e; if (total == 0) return true; vector<int> candidates; for (int i=1; i<=n/2; ++i){ if (total * i % n == 0) candidates.push_back(i); } if (candidates.size() == 0) return false; vector<unordered_set<int>> possible(total/2+1); possible[0].insert(0); for (int num: nums){ for (int i=total/2; i>=1; --i){ for (int t: possible[i-1]){ possible[i].insert(t + num); } } } for (int e: candidates){ if (possible[e].find(total * e / n) != possible[e].end()) return true; } return false; } };
Editor is loading...