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.

Answer 3

This is how you do it. Or at least its a naive solution.

Firstly you order the numbers in ascending order. Assuming A is the ordered result list and S is the set of minimal numbers from which you can construct A.

Loop through A. While there doesn't exist a subset of S that adds up to a_i add a new number to S such that it does.

On the first iteration this will add min(A). The second number is probably going to be in S. This is quite computationally intensive because for each number you examine in A you will need to make sure that there exists a subset of S that adds to it and that you don't add a number that creates a subset of S that adds to something in A.

You can optimize this somewhat by, each time you add a number to S, you work out all possible sums including that new element and removing them from A. Keep going until you empty A.

It gets complicated if the numbers can be negative but you'll see this because there'll have to be a negative element of A for this to be possible.

Answer 4

As GMan has pointed out, this seems at least related to the subset sum problem. Various algorithms suggested here involve asking if a given integer x in the big list X is a sum of some subset of integers in the "current" spanning set S, and if not, then add x to S and remove it from X and continue. It seems like each of these steps is an instance of the subset sum problem, but I cannot prove it.