モジュロでサブセット和バリアント

Question

整数Aと整数N、Mの配列が与えられています。ここで、（sum（S）mod M = N）whereのすべてのサブセットSを探したいと思います。 Aは同じ値の複数の整数を持つことができます。 私の場合、Nは0の範囲になります< = n < = 31、Mは32、Aはnと同じ範囲の整数を含みます。

これを行うには良い/「速い」方法がありますか？

ありがとうございます！

Answer 1

それはO（2 ^N/2ログ（2 ^N/2））= O（2 ^N/2（N/2））、あなたの制約を持つこの作品で解けるですC++上では1秒未満です。

必要なのは、次のとおりです。

1）配列の最初のn/2要素のすべての可能な合計を計算し、合計は、アレイ

2の左部分に表示される場所left[sum] =回数map<int, int> leftに入れ）配列の最後のn/2要素のすべての可能な合計を計算し、各サムのためにSチェックがマップleftは、あなたがbitmasを使用する可能性のあるすべての合計を見つけるために(N - S + M)%M

が値を含んでいませんks：

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]