Adding Combinations of Numbers in an Array Could someone help me optimize this code for time complexity? What is the best way to do this that doesn't include nested for loops?


  Take an array of integers and return a list of sums of every combination
  of 2 numbers. So, for this array [1,2,3], spit out "3,4,5 (1+2, 1+3, 2+3)."


Here is a possible solution using \$O(n^2)\$ time complexity:

static List&lt;int&gt; returnSums(int[] integers) 
{ 
    List&lt;int&gt; sums = new List&lt;int&gt;(); 
    for (int x = 0; x &lt; integers.Length; x++) 
    {
        for (int y = x + 1; y &lt; integers.Length; y++)
        {
            sums.Add(integers[x] + integers[y]);
        } 
    } 
    return sums;
}


Is there a way to write this with \$O(n)\$?
The code is fine, and asymptotically optimal. There is a potential speedup by preallocating the output list to the correct size, but it's at best a factor of 2. VisualMelon's comment is unnecessarily pessimistic: List&lt;T&gt;.Add has an amortised cost of \$O(1)\$, although to show that it's necessary to rely on implementation details which are not in the API documentation.

There are some small improvements which could be made. The spec asks for "a list" rather than "a List", so I see no reason not to follow the principle of coding to the interface. I would prefer to return IList&lt;int&gt; or IReadOnlyList&lt;int&gt;.

The other thing is names. The return in returnSums doesn't tell me anything useful. How about pairwiseSums? And instead of x and y I would use i and j, which are de facto standard variable names for array indices for reasons going back to FORTRAN's type system.