带模的子集和变体

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] =

2）计算n/2数组最后一个元素的所有可能的总和，并针对每个总和S检查映射是否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];
}