An algorithm to find a pair of sums from a list of numbers?

Question

Suppose you have the following list of numbers, {3,6,10,9,13,16,19}, not necessarily in that order. Now, not knowing that this is the set of the possible combination of the set {3,6,10}, is there an algorithm, in any programming language that can be used to find these combination efficiently. Basically, I want to recover the list from the total set - where all numbers are included. What is an efficient algorithm, I do not wish to reinvent the wheel if one already exists?

Answer 1

For the general case where there can be any number of elements, here is an O(q * log(q)) algorithm where q is the size of the input list:

1. Sort the list q in ascending order.
2. Remove the smallest element, m, and add it to the result set. Remove it from q.
3. Iterate over q. Keep a list of numbers that we've seen. If we see a number that is (a number we've already seen + m) then discard it. This should keep half the numbers (all those that don't involve m).
4. Repeat from step 2 until all numbers are found.

Here's an implementation of this algorithm in Python:

def solve(q):
    q = sorted(q)
    x = []
    while q:
        x.append(q[0])

        s = [False]*len(q)
        s[0] = True
        j = 1

        for i in range(1, len(q)):
            if q[i] == q[0] + q[j]:
                s[i] = True
                j += 1
                while j < len(q) and s[j]:
                    j += 1

        q = [k for k, v in zip(q, s) if not v]
    return x

s = [1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99]
from itertools import combinations
q = list(sum(x) for r in range(1, len(s) + 1) for x in combinations(s, r))
print(solve(q))

Result:

[1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99]

---

Original answer:

Assuming that there are only 3 numbers in the list, and that no number can be negative:

Two of the numbers must be the smallest two numbers in the list. The largest number must be the sum of all three. By subtraction you can find the third number.

Answer 2

1) Find the smallest two numbers, these must be a part of the original list.

2) Find their sum, everything smaller in the list must be part of the original list.

3) Find the next smallest sum and repeat until all sums of two numbers are done.

Any time you add a number to the original list or find a sum, remove it from the big list.

4) Continue with 3 number sums, and keep increasing until the big list is empty.

Edit:

Finding the next smallest sum requires a sorted list of your numbers. If your list is A,B,C,D,E then then smallest sum is A+B and the next smallest sum is A+C.

The performance is as terrible as it gets: 2^N, but if I'm reading your question right, the list contains your original list and all possible sums, which would allow you to increase performance considerably.

For instance, you know how many numbers you are looking for, which means you know when you only need one more, and since you also know the largest number in the list, the last number is the largest number minus all numbers already added to your original list.