algorithm - 带模的子集和变体

Question

给定一个整数数组 A 和整数 N、M。我想找到 A 的所有子集 S，其中 (sum(S) mod M = N)。A 可以有多个相同值的整数。在我的例子中，N 将在 0<=n<=31 范围内，M 将是 32，A 将包含与 n 相同范围内的整数。

有什么好的/“快速”的方法可以做到这一点吗？

谢谢!

Answer 1

它在 O(2^n/2 log₂(2^n/2)) = O(2 ^n/2 (n/2))，在你的约束下，这在 C++ 上的工作时间不到一秒。

您只需要:

1) 计算第一个 n/2 的所有可能总和数组的元素并将它们放入 map<int, int> left其中 left[sum] = sum出现在数组左边多少次

2) 计算最后 n/2 的所有可能总和数组的元素和每个总和 S检查 map left包含值 (N - S + M)%M

要找到所有可能的总和，您可以使用位掩码:

for (int mask = 1; mask < pow(2, n/2); mask++) {
    int sum = 0;
    for (int i = 0; i < n/2; i++)
        if ( (int) (mask & (1<<i)) ) 
            sum += A[i];
}