CODEWITHSUNDEEP
calgorithmmath
user318747
user318747

Reputation: 1428

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 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

Upvotes: 0

Views: 115

Answers (1)

moinudin
moinudin

Reputation: 138347

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.

Upvotes: 4

Related Questions