# Three Sum

This problem is modified from the following leetcode link.

Leetcode link: https://leetcode.com/problems/3sum/

## #

QuestionGiven an array `nums`

of *n* integers, are there elements *a*, *b*, *c* in `nums`

such that *a* + *b* + *c* = target?

Find all triplets in the array which gives the sum of the target (you may assume that there are only unique triplets).

Hint: Think how we can build upon our solution in the Two-Sum problem.

## #

Method 1: Brute ForceAs with any problem, we always start off with the brute force technique. What is the simplest way to get the answer out, without any concern about the time complexity etc.?

We can simply use 3 for-loops and find out the indices like in our twoSum problem.

This will give us the right results, but such a method will be a poor solution for a huge array. Though space complexity is in constant time of O(1), with 3 for-loops we have a time complexity of O(n^{3}).

## #

Method 2: Reuse our twoSum functionDoes the problem seem familiar? The three sum problem is very much like the two sum, just that we are finding 3 numbers instead of 2. A great way to solve this problem is to use the `twoSum`

method we wrote with slight modifications.

The `twoSum`

method will now just use a set instead of a dictionary as we don't need to return the indices anymore.

Let's write our `threeSum`

function now.

In each iteration, we calculate what is the `required`

target we need to find a pair from. And we use our `twoSum`

function to find that pair. If we do find a pair, we add it to our list of triplets.

Note that we are slicing the array to find the pair from using `sums[i+1:]`

. This will search a subarray of the numbers as we keep moving forward in the iteration.

Finally, we return the `triplets`

which has the list of triplets we found.

This yields a time complexity of O(n^{2}) since for each element we have a subarray we need to search through for a pair. We will have a space complexity of O(n) from the `twoSum`

method.