题目

示例

思路

数组分为 两个组，使得两个数组的平均值相同

可以使用递归的方法，枚举每一个元素的归属组合，并寻找符合要求的一个组合，但是会超时。。。。。

代码

bool dfs(int *nums, int numsSize, int index, float leftSum, float leftCount, float rightSum, float rightCount) 
{
    if (leftSum / leftCount == rightSum / rightCount) {
        return true;
    }//满足条件
    for (int i = index; i < numsSize; i++) {
        if (dfs(nums, numsSize, i+1, leftSum + nums[i], leftCount + 1, rightSum - nums[i], rightCount -1) == true) {
            return true;
        }//枚举每一个状态
    }
    return false;
}

bool splitArraySameAverage(int* nums, int numsSize){
    int sum = 0;
    for (int i = 0; i < numsSize; ++i) {
        sum += nums[i];
    }//记录前缀和，方便比较
    return dfs(nums, numsSize, 0, 0, 0, sum, numsSize);//递归回溯
}

作者：小迅
链接：https://leetcode.cn/problems/split-array-with-same-average/solutions/1967340/by-xun-ge-v-hbqj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    bool splitArraySameAverage(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return false;
        int s = accumulate(nums.begin(), nums.end(), 0);
        for (int& v : nums) v = v * n - s;
        int m = n >> 1;
        unordered_set<int> vis;
        for (int i = 1; i < 1 << m; ++i) {
            int t = 0;
            for (int j = 0; j < m; ++j) if (i >> j & 1) t += nums[j];
            if (t == 0) return true;
            vis.insert(t);
        }
        for (int i = 1; i < 1 << (n - m); ++i) {
            int t = 0;
            for (int j = 0; j < (n - m); ++j) if (i >> j & 1) t += nums[m + j];
            if (t == 0 || (i != (1 << (n - m)) - 1 && vis.count(-t))) return true;
        }
        return false;
    }
};



作者：小迅
链接：https://leetcode.cn/problems/split-array-with-same-average/solutions/1967340/by-xun-ge-v-hbqj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。