Adding Combinations of Numbers in an Array

Question

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<int> returnSums(int[] integers) 
{ 
    List<int> sums = new List<int>(); 
    for (int x = 0; x < integers.Length; x++) 
    {
        for (int y = x + 1; y < integers.Length; y++)
        {
            sums.Add(integers[x] + integers[y]);
        } 
    } 
    return sums;
}

Is there a way to write this with \$O(n)\$?

Answer 1

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<T>.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<int> or IReadOnlyList<int>.

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.

Answer 2

I don't think you can do this without nested loops.

This

x < integers.Length

Can be

x < integers.Length - 1 

But is will not save much

Return IEnumerable if you can

You can spare an array lookup

This is how I would write this

static IEnumerable<int> returnSums(int[] integers)
{
    for (int i = 0; i < integers.Length - 1; i++)
    {
        int outer = integers[i];
        for (int j = i + 1; j < integers.Length; j++)
        {
            yield return outer + integers[j];
        }
    }
}