Subset sum $O(n)$ complexity

Question

I want to resolve a variation of the subset sum problem, that is : from a set of naturals A, see if it exists a subset of two elements of A whose sum is equal to the natural t.

I saw some algorithms with a complexity of $O(2^n)$ but not with $O(n)$. Is such algorithm exists?

I do not understand how the subset sum algorithm works; I read this one, but it is not clear to me. Can anyone comment on this, please?

Answer 1

A brute-force solution (trying all pairs) would have complexity $O(n^2)$.

A more efficient solution is by

• sorting all elements,
• scanning the array from both ends, making sure that the right element $e_r$ is always the smallest such that $e_l+e_r\ge t$. (This step is done in linear time.)

This has the complexity of sorting.

---

In practice, you might do better with a hash table:

• enter all keys in the table,
• for every key $k$, lookup $t-k$.

But the worst case can be... worse.