CODEWITHSUNDEEP
algorithmdynamic-programmingsubset-sum
Anton Andell
Anton Andell

Reputation: 93

Subset sum variant with modulo

Given an array of integers A and integers N, M. I want to find all the subsets S of A where (sum(S) mod M = N). A can have multiple integers of the same value. In my case N will be in the range 0<=n<=31, M will be 32 and A will contain integers in the same range as n.

Is there any good/"fast" way to do this?

Thanks!

Upvotes: 5

Views: 1901

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

If you'd just like to count them, we can solve it in O(|A| * M) with dynamic programming. Here's an example:

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 code:

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


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

Upvotes: 2

Wsl_F
Wsl_F

Reputation: 842

It is solvable in O(2n/2 log2(2n/2)) = O(2n/2 (n/2)), with your constrains this works on C++ less than a second.

All you need is:

1) compute all possible sums of first n/2 elements of the array and put them in map<int, int> left where left[sum] = how many times sum appears at the left part of the array

2) compute all possible sums of last n/2 elements of the array and for each sum S check does map left contains value (N - S + M)%M

to find all possible sums you could use bitmasks:

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];
}

Upvotes: 2

Related Questions