Intuition

To split the array into two non-empty groups with the same average, we need to find a non-empty subset whose sum is proportional to its size, matching the overall average. By scaling the problem to subset sums, we can use dynamic programming and bitmasking to efficiently check all possible subset sizes and sums.

Approach

Let n be the length of nums and s be the total sum.
For each possible subset size k from 1 to n//2:
- The subset sum must be s * k / n and must be integer.
- Use DP to check if any subset of size k has sum s * k / n.
Use a set to store all possible sums for each subset size using bitmask DP.
If any valid subset is found, return True; otherwise, return False.

Code

[{"language":"C++","code":"#include <vector>\n#include <unordered_set>\nusing namespace std;\nclass Solution {\npublic:\n    bool splitArraySameAverage(vector<int>& nums) {\n        int n = nums.size(), s = 0;\n        for (int x : nums) s += x;\n        vector<unordered_set<int>> dp(n+1);\n        dp[0].insert(0);\n        for (int x : nums) {\n            for (int k = n-1; k >= 0; --k) {\n                for (int sum : dp[k]) {\n                    dp[k+1].insert(sum + x);\n                }\n            }\n        }\n        for (int k = 1; k <= n/2; ++k) {\n            if ((s * k) % n == 0 && dp[k].count(s * k / n)) return true;\n        }\n        return false;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func splitArraySameAverage(nums []int) bool {\n    n, s := len(nums), 0\n    for _, x := range nums {\n        s += x\n    }\n    dp := make([]map[int]struct{}, n+1)\n    for i := range dp {\n        dp[i] = make(map[int]struct{})\n    }\n    dp[0][0] = struct{}{}\n    for _, x := range nums {\n        for k := n - 1; k >= 0; k-- {\n            for sum := range dp[k] {\n                dp[k+1][sum+x] = struct{}{}\n            }\n        }\n    }\n    for k := 1; k <= n/2; k++ {\n        if (s*k)%n == 0 {\n            if _, ok := dp[k][s*k/n]; ok {\n                return true\n            }\n        }\n    }\n    return false\n}","lang":"go"},{"language":"Java","code":"import java.util.*;\nclass Solution {\n    public boolean splitArraySameAverage(int[] nums) {\n        int n = nums.length, s = 0;\n        for (int x : nums) s += x;\n        Set<Integer>[] dp = new Set[n+1];\n        for (int i = 0; i <= n; ++i) dp[i] = new HashSet<>();\n        dp[0].add(0);\n        for (int x : nums) {\n            for (int k = n-1; k >= 0; --k) {\n                for (int sum : dp[k]) {\n                    dp[k+1].add(sum + x);\n                }\n            }\n        }\n        for (int k = 1; k <= n/2; ++k) {\n            if ((s * k) % n == 0 && dp[k].contains(s * k / n)) return true;\n        }\n        return false;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun splitArraySameAverage(nums: IntArray): Boolean {\n        val n = nums.size\n        val s = nums.sum()\n        val dp = Array(n+1) { mutableSetOf<Int>() }\n        dp[0].add(0)\n        for (x in nums) {\n            for (k in n-1 downTo 0) {\n                for (sum in dp[k]) {\n                    dp[k+1].add(sum + x)\n                }\n            }\n        }\n        for (k in 1..n/2) {\n            if ((s * k) % n == 0 && dp[k].contains(s * k / n)) return true\n        }\n        return false\n    }\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n    def splitArraySameAverage(self, nums: list[int]) -> bool:\n        n, s = len(nums), sum(nums)\n        dp = [set() for _ in range(n+1)]\n        dp[0].add(0)\n        for x in nums:\n            for k in range(n-1, -1, -1):\n                for total in dp[k]:\n                    dp[k+1].add(total + x)\n        for k in range(1, n//2+1):\n            if (s * k) % n == 0 and (s * k // n) in dp[k]:\n                return True\

Related Tags