<p>Use the standard meet-in-the-middle algorithm with complexity <span class="math-container">$O(2^{N/2})$</span>.  Contrary to what you wrote, it is not hard to implement.  It involves building two lists of size <span class="math-container">$2^{20}$</span> (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.</p>

CC BY-SA 4.0
2022-02-28T06:56:36.507Z
2022-02-28T06:56:36.507Z
D.W.
<p>Does anyone have any ideas for this algorithms problem?</p>
<p>Given an array <span class="math-container">$A$</span> with 40 integers (<span class="math-container">$-10^9 &lt; A_i &lt; 10^9$</span>), how many ways are there to reach a target sum <span class="math-container">$X$</span>.</p>
<p>Normally, I would use dynamic programming, however the space complexity is too large, as a <span class="math-container">$10^9$</span> array would give me a runtime error.</p>
<p>The brute force would obviously not work as <span class="math-container">$2^{40}$</span> is far too large. There is an algorithm that in theory works in <span class="math-container">$O(2^{N/2})$</span> which would work in this scenario, however it seems far too complicated for this problem.</p>
<p>Is there another approach or optimization that I am missing?
Note: the solution should have <span class="math-container">$10^8$</span> or less operations</p>

CC BY-SA 4.0
2022-02-27T23:20:56.667Z
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?
Neal Young
<cc.complexity-theory><ds.algorithms>
Interesting Variation on Subset Sum Problem
user65953
# Interesting Variation on Subset Sum Problem

(Asked by: username_0 on 2022-02-25)

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

**Tags:** cc.complexity-theory, ds.algorithms

> **Comments:**
> **username_1**: 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?  

---

## 1 answers

### Answer by username_2 on 2022-02-28. Score: 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.


---

