不少人在 LeetCode 上刷到 805 题时第一反应都是枚举所有子集两边各算一次平均值不就行了。我最早也是这么写的本地小数据随便过一提交就直接超时——数组长度给到 302^30 差不多十亿个子集别说 Java换 C 也一样得挂。真正让这题变得可写的不是暴力技巧而是把两个子集均值相等这句话翻译成一个可判定的等式能不能挑出 k 个数让它们的和恰好等于 k·S/n。一旦看清这一点题目就从枚举集合变成了按元素个数分层的 0/1 子集和背包也就是splitArraySameAverage(int[] nums)这个boolean方法真正要解决的核心问题。这篇内容会从数学等价转换、背包状态设计、BitSet 加速、折半枚举备选方案一直讲到我在这题上真真切切踩过的几个坑适合刚接触子集和类 DP 的读者也适合已经被这题卡过一轮的人回头对照。1. 先把两边均值相等变成一句能判定的等式1.1 用交叉相乘把除法消掉s k·S/n设数组长度为 n所有元素之和为 S。假设我们能把数组拆成两个非空子集 A 和 B其中 A 的大小是 kA 的元素和是 s。那么 B 的大小自然就是 n - kB 的元素和就是 S - s。所谓两个子集均值相等写成式子就是s / k (S - s) / (n - k)这里 k 和 n - k 都大于 0因为两个子集都必须非空分母不会出现 0 的情况。两边交叉相乘s * (n - k) (S - s) * k s * n - s * k S * k - s * k左右两边各有一个- s * k直接抵消剩下s * n S * k → s k * S / n这一步是整个题目的钥匙。它告诉你一件很反直觉的事你根本不需要关心另一个子集长什么样。只要你能找到一个大小为 k、和恰好等于k * S / n的子集剩下的元素自动构成另一个合法子集因为它们的平均值会被上面的等式强制绑在一起。这就是互补这个性质的价值——把同时满足两个约束降维成满足一个约束。顺带一个必须注意的推论既然s k * S / n而 s 一定是整数那么k * S 必须能被 n 整除否则这个 k 连候选资格都没有。这条推论后面会变成一条几乎零成本的剪枝。1.2 为什么只需要看 k ≤ n/2 的那一半有人会问k 从 1 到 n-1 都有可能是答案为什么很多题解只枚举到 n/2理由还是互补性。假设存在一个合法的解它的子集大小 k 满足 k n/2。那么这个子集的补集大小就是 n - k它同样满足(n - k) * S / n这个和的条件因为它的和是S - k*S/n (n-k)*S/n。而 n - k n/2且 n - k ≥ 1。换句话说任何一个大小为 k 的解都能找到一个大小为 n - k 的解与其对应一大一小永远成对出现。所以只需要在 k ∈ [1, n/2] 这个区间里找就够了搜索空间直接砍掉一半。这个对称性在写代码时非常关键不只是省时间的问题——后面 4.1 小节里那个把整数组当答案的坑正是靠这个上界顺手挡掉的。1.3 一个几乎不要钱的整除剪枝在真正建 DP 表之前可以先花 O(n) 的时间做一次预判遍历 k 从 1 到 n/2看是否存在某个 k 使得k * S % n 0。如果全都不成立说明任何一个子集大小都无法对应整数目标和那答案必然是false直接返回。数组长度才 30这个