Interesting Variation on Subset Sum Problem

Question

Does anyone have any ideas for this algorithms problem?

Given an array $A$ with 40 integers ($-10^9 < A_i < 10^9$), how many ways are there to reach a target sum $X$.

Normally, I would use dynamic programming, however the space complexity is too large, as a $10^9$ array would give me a runtime error.

The brute force would obviously not work as $2^{40}$ is far too large. There is an algorithm that in theory works in $O(2^{N/2})$ which would work in this scenario, however it seems far too complicated for this problem.

Is there another approach or optimization that I am missing? Note: the solution should have $10^8$ or less operations

Answer 1

Use the standard meet-in-the-middle algorithm with complexity $O(2^{N/2})$. Contrary to what you wrote, it is not hard to implement. It involves building two lists of size $2^{20}$ (by brute-force enumeration of possibilities), sorting them, then doing a linear-time merge over them. This is easy to implement, and if you're not willing to do that much implementation work, then there is no solution you will be happy with.