-3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ You specify that you are interested only in instances of size 40 only, which suggests that you are interested in solving instances in practice.. Are you interested in an algorithm that can solve any such instance in the kind of time you have in mind? Or do you just have in mind just one particular instance? Or some restricted family of instances? Each of these possibilities probably leads to a different answer. So please clarify as much as possible what instances you want to solve. Also, $10^9 = 1G$, much smaller than typical RAM these days, so why a runtime error? $\endgroup$
    – Neal Young
    Feb 27 at 23:20

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.