java - 检查是否有一个数组的大小为 k 的子集具有 n 的和倍数

Question

晚上好，我在 Java 中有一个包含 n 整数的数组。我想检查是否有满足条件的条目的大小为 k 的子集:

k 个条目的总和是 m 的倍数。

我怎样才能尽可能高效地做到这一点？我需要检查 n!/k!(n-k)! 个子集。

Answer 1

您可以使用动态规划。状态是(前缀长度，求和模 m，子集中的元素数)。转换很明显:我们要么再添加一个数字(增加子集中的元素数量并计算新的求和模 m)，要么只增加前缀长度(不添加当前数字)。如果您只需要一个是/否答案，您可以只存储最后一层值并应用位优化来更快地计算转换。时间复杂度为 O(n * m * k)，或大约 n * m * k/64 位优化操作。空间复杂度为 O(m * k)。对于几千个元素，它看起来是可行的。我所说的位优化是指使用 C++ 中的 bitset 之类的东西，它可以使用按位运算同时对一组位执行操作。