summing multiple sets

If I have several sets of numbers (just a 2D array where each row is a set):

 [ 1, 3, -1, -1]
 [ 2, 4, -1, -1]
 [ 7, 8, 9, 10]

What would be an algorithm to create a list of sums (ignoring -1's)? the result 开发者_Python百科for the above would be:

1+2+7,
1+2+8,
1+2+9,
1+2+10,
1+4+7,
1+4+8,
1+4+9,
1+4+10,
3+2+7,
3+2+8,
3+2+9,
3+2+10,
3+4+7,
3+4+8,
3+4+9,
3+4+10

---

For each number in the first list, generate all sums starting with that number and all sums recursively generated by applying the same method to all but the first list. When you have no lists left, that is the base case.

Pseudo-code:

function find_sums(lists):
    if lists is empty:
        return [""]
    sums = []
    for n in lists[0]:
        if n != -1:
            for sum in find_sums(lists from index 1 onwards):
                sums.append(n + "+" + sum)
    return sums

This is called the Cartesian product.