# 3 Sum

Given an array S of n integers, are there elements a, b, c in S such that \
a + b + c = 0? \
\
Find all unique triplets in the array which gives the sum of zero.

> Note: The solution set must not contain duplicate triplets.

For example, given array

> S = \[-1, 0, 1, 2, -1, -4]

A solution set is:

> ```
> [ [-1, 0, 1], [-1, -1, 2] ]
> ```

{% tabs %}
{% tab title="Scala" %}

```scala
def threeSum(nums: Array[Int]):List[(Int,Int,Int)] = {
  scala.util.Sorting.quickSort(nums)
  var i,j,k,target: Int = 0
  j = nums.length - 1
  var ret = List[(Int,Int,Int)]()
  for (i <- 0 until nums.length) {
    k = i + 1
    j = nums.length - 1
    target = 0 - nums(i)
    while (k < j) {
      nums(j) + nums(k) match {
        case n if n == target => {
          ret = Tuple3(nums(i),nums(k),nums(j)) :: ret
          while (k < j && nums(k) == nums(k+1)) k += 1
          while (k < j && nums(j) == nums(j-1)) j -= 1
          j -= 1
          k += 1
        }
        case n if n > target => j -= 1
        case n if n < target => k += 1
      }
    }
  }
  ret
}

threeSum(Array(0,-1,2,3,4,5,6,1))
```

{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}