##
### Problem statement

Find all the pairs of numbers in an *unsorted array `arr`* that sum to a given number `target`.

For example, if the array is `[3, 5, 2, -4, 8, 11]` and the sum is `7`, your program should return `[[11, -4], [2, 5]]` because `11 + -4 = 7` and `2 + 5 = 7`.

##
### Solution statement

There can be two approaches to solve this problem:

1. Naive approach
2. Efficient approach

###
#### 1. Naive approach

The Naive approach would be to choose an element (`e`) from `arr` and loop through the rest of it to see if the sum of (`e`) and some other element $e^{'}$ equals the target. 

However, this will result in the time complexity of $O(n^{2})$, which is inefficient.

##
### Code
###
#### Example 1

The Python program below implements the algorithm using the Naive approach:

def twoSum (arr, target):
	res = []
	for i in range(len(arr)):
		for j in range(i, len(arr)):
			if arr[i] + arr[j] == target:
				res.append([arr[i], arr[j]])
	return res

def main ():
	arr = [3, 5, 2, -4, 8, 11]
	target = 7
	print(twoSum(arr, target))
main()

###
#### 2. Efficient approach

We can efficiently solve this problem using sets. We can add every element of `arr` if the `target - arr[i]` value exists in the `sums` set. 

This implies that `target = arr[i] + (the value in sums)`, which this will be a solution. This algorithm will run in $O(n)$.

def twoSum (arr, target):
	res = []
	sums = set()

	for val in arr:
		if target - val in sums:
			res.append([val, target - val])
		sums.add(val)
	return res

def main ():
	arr = [3, 5, 2, -4, 8, 11]
	target = 7
	print(twoSum(arr, target))
main()

How to solve the two-sum problem

Problem statement

Solution statement

1. Naive approach

Code

Example 1

2. Efficient approach

Example 2