0

Does anyone have any ideas for this algorithms problem?

Given an array A with 40 integers (-10^9 < Ai < 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?

Adam Tan
  • 1
  • *how many ways are there to reach a target sum X.* -- Sounds more like a math problem than an algorithm problem. – PaulMcKenzie Feb 25 '22 at 17:40
  • It's not a space complexity problem as you don't need a 10^9 array. It's a time complexity problem as you have 2^40^(number of operators) set of calculations to check. You can turn some of that into space complexity by caching results, and that could get huge. – Joseph Larson Feb 25 '22 at 17:41

0 Answers0