您可以将此问题简化为总和子集问题 -也在此处缓存。这是主意。
设A数组。计算的长度S = A[0] + ... + A[N-1]在哪里。对于从到，让。如果是整数，则找到总和为的大小子集。如果可以这样做，那么您就完成了。如果您不能对任何一个执行此操作，则不存在此类分区。N``A``k``1``N-1``T_k = S * k / N``T_k``A``k``T_k``k
这是这种方法背后的数学原理。假设存在一个A这样的分区，使得两个部分的平均值相同，X即size的大小x，Y而sizey为分区，其中x+y = N。那你一定有
sum(X)/x = sum(Y)/y = (sum(A)-sum(X)) / (N-x)
所以有一点代数
sum(X) = sum(A) * x / N
由于数组包含整数，因此左侧是整数，因此右侧也必须是整数。这激发了T_k = S * k / N必须为整数的约束。剩下的唯一部分是实现T_k为大小子集的总和k。
602392714
清零编程群