Subset sum variant with modulo

Question

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!

Answer 1

It is solvable in O(2^n/2 log₂(2^n/2)) = O(2^n/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];
}