What adds up
===========

Given three arrays of integers your task is to create an algorithm that finds the numbers in the first two arrays whose sum is equal to any number in the third. The return value should be an array containing the values from the argument arrays that adds up. The sort order of the resulting array is not important. If no combination of numbers adds up return a empty array.

### Example
A small example: Given the three input arrays `a1 = [1, 2]; a2 = [4,3]; a3 = [6,5,8]`, we need to find the number pairs from `a1` and `a2` that sum up to a number in `a3` and return those three numbers in an array. In this example, the result from the function would be `[[1, 4, 5] , [2, 4, 6], [2, 3, 5]]`.
```
Given three arrays
a1      a2      a3
 1       4       6          (a1 a2 a3)    (a1 a2 a3)  (a1 a2 a3)
 2       3       5      =>  [[1, 4, 5] ,  [2, 4, 6],  [2, 3, 5]]
                 8
                 
each value in the result array contains one part from each of the arguments.
```

### Testing
A function `compare_array` is given. This function takes two arrays and compares them invariant of sort order.

```python
test.expect(compare_arrays(addsup([1,2], [3,1], [5,4]), [[1,3,4], [2,3,5]]))
```

### Greater goal
For extra honor try and make it as effective as possible. Discuss whats the most effective way of doing this. The fastest way i can do this is in *O(n^2)*. Can you do it quicker?

Difficulty: introductory

Starter code:

def addsup(a1, a2, a3):
	

Solutions:
def addsup(a1, a2, a3):
  return [[x,y,x+y] for x in a1 for y in a2 if x+y in a3]

from itertools import product

def addsup(a1, a2, a3):
    goal = set(a3).__contains__
    return [[x, y, x+y] for x,y in product(a1, a2) if goal(x+y)]

def addsup(a, b, t):
    t = set(t)
    return [[m, n, m+n] for m in a for n in b if m + n in t]

def addsup(a1, a2, a3):
    a3 = set(a3)
    return [[x1, x2, x1 + x2] for x1 in a1 for x2 in a2 if x1 + x2 in a3]

def addsup(a1, a2, a3):
    r = {}
    for s in a3:
      for i in a1:
          r[s-i] = [i] + r.get(s-i, [])
    result = []
    for j in a2:
        if j in r:
            for i in r[j]:
                result.append([i, j, j+i])
    return result

def addsup(a1, a2, a3):
    sums = []
    # test every possible combination of a1 and a2, if sum in a3, append to result list
    for i in a1:
        for j in a2:
            if (i+j) in a3:
                sums.append([i, j, i+j])
    return sums

def addsup(a1, a2, a3):
    results = []
    for ele1 in a1:
        for ele2 in a2:
            if ele1+ele2 in a3:
                results.append([ele1, ele2, ele1+ele2])
    return results

addsup = lambda a1, a2, a3: [[x, y, x + y] for x in a1 for y in a2 if x + y in a3]

def addsup(a1, a2, a3):
  l = [[c-b,b,c] for b in a2 for c in a3]
  return list(filter((lambda e: e[0] in a1), l))

def addsup(a1, a2, a3):
    a4 = []
    for n1 in a1:
        for n2 in a2:
            if n1 + n2 in a3:
                a4.append([n1, n2, n1 + n2])
    return a4