Untitled

 avatar
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...