题目描述

文字版

代码

class Solution {
public:
    vector<int> nums;
    // 存储相同元素
    unordered_multiset<int> S;

    // 枚举相加结果 
    void dfs1(int u, int n, int sum) {
        // 结果有相同值
        if (u == n) S.insert(sum);
        else {
            // 不要当前数
            dfs1(u + 1, n, sum);
            // 要当前数
            dfs1(u + 1, n, sum + nums[u]);
        }
    }

    // u左边的当前位置 n左边的个数 sum左边个数的结果 cnt左边当前的个数
    bool dfs2(int u, int n, int sum, int cnt) {
        if (u == n) {
            // cnt不能取空集和全集
            // 如果包含左边的相反数S.count(-sum)
            if (cnt && cnt < n && S.count(-sum)) return true;
            return false;
        } else {
            // 不要当前数
            if (dfs2(u + 1, n, sum, cnt)) return true;
            // 要当前数
            if (dfs2(u + 1, n, sum + nums[u], cnt + 1)) return true;
            return false;
        }
    }

    bool splitArraySameAverage(vector<int>& _nums) {
        nums = _nums;
        int n = nums.size();
        if (n == 1) return false;
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // 每一个数乘以偏移量n 这样做最终结果不改变
        // x * n - (sum * n) / n;
        // 减去平均数 映射数值 映射后所有数相加为0
        // 这样就可以判断两边相加是否为0
        // 等价于题目的两数组平均值相等
        for (auto& x: nums) x = x * n - sum;

        // 折半搜索
        int m = n / 2;
        // 生成右边所有结果
        dfs1(m, n, 0);

        int s1 = 0, s2 = accumulate(nums.begin() + m, nums.begin() + n, 0);
        // [18,0,16,2]
        // 如果左边取空集 右边取全部
        // 则先要将右边的空集去掉
        S.erase(S.find(s1));
        // 剩下的0就是右边取全部的结果
        // 和左边的空集0 相加等于0 是一个合法解
        if (S.count(0)) return true;
        // 如果左边取全部 右边取空集
        // 则先要将右边的空集加上 将右边的全部去掉
        S.insert(s1), S.erase(S.find(s2));
        // 在集合中找到左边取全部的相反数
        // 如果存在 则证明左右相加等于0
        if (S.count(-accumulate(nums.begin(), nums.begin() + m, 0))) return true;
        // 枚举是否存在左边的相反数
        return dfs2(0, m, 0, 0);
    }
};