모듈로를 가진 부분 합계 변형

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 로그 (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

가능한 모든 합계는 bitmas을 사용할 수를 찾을 수 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 

파이썬 코드 :

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]