count all subsets of integers (including negative) that sum to x

Question

I am given an array of max length 40 containing integers in [-10^9;10^9]. I am also given the expected sum X which lies in [0;10^9]. Now I am supposed to give the total amount of subsets that sum to X. I can't figure out a way to deal with the negative numbers. I first tried the brute-force approach which works fine for small input arrays but is unusable for large ones:

auto r = 0ULL;
for(auto i = 0ULL; i < (1ULL << n) - 1ULL; ++i) {
    auto x = 0ULL;
    for(auto j = 0ULL; j < n; ++j) {
        if(i & (1ULL << j)) {
            x += values[j];
        }
    }
    r += x == sum;
}
cout << r << '\n';

Then I tried memorizing the intermediate results of the additions so I don't have to calculate them more then once for the same elements. But that consumes ALOT of space ( should be around 9 TB for inputs of length 40 x) ). Can someone give me a hint on a better approach?

Answer 1

Sum range and item count looks too large for dynamic programming due to memory reason.

But limit of 40 items allows to apply something like "meet-in-the-middle" principle.

Separate the first 20 items and count sums for all possible subsets - just walk through 2^20 subsets (including empty one!) (using recursion or binary representation of subset number or some other way) and write sums in the map containing pairs (sum, count).

Do the same for the second half. Note that size of maps is quite reliable.

Walk though the first map keys and look for corresponding keys from the second map. Pseudocode:

for sum in map1:
    if map2.contains(X - sum):
        result += map1[sum] * map2[X - sum]