具有模数的子集和变量

Question

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

有没有好/“快”的方法来做到这一点？

谢谢！

Answer 1

它可以在O（2n / 2 log2（2n / 2））= O（2n / 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];
}

Answer 2

如果您只想计算它们，我们可以使用动态编程在O(|A| * M)中解决它。这是一个例子：

A = [2, 6, 4, 3]
M = 5

    0 1 2 3 4
S = 0 0 0 0 0 // The number of subsets with sum i (mod M)

// Iterate over A (through S each time)
2   0 0 1 0 0
6   0 1 1 1 0
4   1 2 2 1 1
3   3 3 3 3 3

Python代码：

A = [2, 6, 4, 3]
M = 5
S = [0 for i in xrange(0, M)]
STemp = [0 for i in xrange(0, M)]

for a in A:
  for (i, v) in enumerate(S):
    ii = (a + i) % M
    STemp[ii] = S[ii] + v
  STemp[a % M] = STemp[a % M] + 1
  S = STemp
  STemp = [0 for i in xrange(0,M)]

print S  # [3, 3, 3, 3, 3]