# Possible to get the Sum x with maximal two summands? [duplicate]

Suppose we have $$n$$ different summands. Is it possible to get the sum x with a maximum of two of the $$n$$ summands (Below the m summands there can be several times the same one). For example you have the summands (2,4,6,7). So its possible to get the sum $$2+4 =6$$,$$6=6$$ but its impossible to get the sum $$3$$ or $$1$$ ect.

My idea of an algorithm would have the runtime $$\mathcal{O}(n\log(n))$$. Now I'm not sure if this is already aymptotically optimal ?

## marked as duplicate by Yuval Filmus algorithms StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Dec 9 '18 at 1:17

• Not sure what you are asking. Is the sum of the two largest summands the maximum you wanted? You can find those two in $O(n)$. – Apass.Jack Nov 8 '18 at 20:20
If the numbers have a limit on their value, i.e. all numbers are smaller than $$m$$, then you can get runtime of $$O(n + m)$$: in an array $$t$$ of size $$m$$, for each number $$a$$ in the set of summands, check if $$t[x - a] > 0$$: if yes, then the answer is $$(a, x - a)$$. If not, set $$t[a] = 1$$ and continue with the next number.
This can be slightly improved with assigning values in buckets, but the worst time complexity will be $$O(nm)$$.
Otherwise, $$O(n \log n)$$ is the optimal complexity.