# 0015. 3Sum

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - 3Sum](https://leetcode.com/problems/3sum/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0015-3-sum)

Given an integer array nums, return all the triplets `[nums[i], nums[j], nums[k]]` **such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`**

**Notice that the solution set must not contain duplicate triplets.**
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `0 <= nums.length <= 3000`
* `-10^5 <= nums[i] <= 10^5`

```
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Input: nums = []
Output: []

Input: nums = [0]
Output: []
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
**Same idea as** [**0001. Two Sum**](https://yyloumike.gitbook.io/leetcode/mixed-design/two-sum-4-qs/0001.-two-sum) with **more case handlings.**
{% endhint %}

There are **several different cases** for the sum of three numbers that equal ZERO.

* 0, 0, 0
* -n, 0, n
* -n, -m, m+n
* -n-m, n, m

We need to use a **specific data structure (Set in Python)** to solve this problem with an extra constraint that **the solution set must not contain duplicate triplets.**

We store negative numbers, ZERO, positive numbers into a list and a set separately. Then, **we use the numbers stored in the list to calculate the remaining value and then search it in the Set.** Once we find it, we add it to the other Set as the final answer.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # (base case)
        if len(nums)  < 3: return []
        if len(nums) == 3: return [nums] if sum(nums) == 0 else []
        
        # ==================================================
        #  Math + Set                                      =
        # ==================================================
        # time  : O(n^2)
        # space : O(n) 
        
        zero, negative, positive = [], [], []
        for num in nums:
            if num > 0: positive.append(num)
            elif num < 0: negative.append(num)
            else: zero.append(num)
                
        # (case handling)
        if len(negative) == 0:
            if len(zero) == 0: return []
            if len(positive) == 0 and len(zero) < 3: return []
            if len(positive) == 0 and len(zero) == 3: return [[0, 0, 0]]
        
        ans = set()
        negSet = set(negative)
        posSet = set(positive)
        
        if len(zero) > 2: ans.add((0, 0, 0))
        
        # (-n, n, 0)
        if zero:
            for num in negSet:
                if -num in posSet: ans.add((num, -num, 0))
        
        # (-n, -m, n+m)
        for i in range(len(negative)):
            for j in range(i+1, len(negative)):
                remain = -1 * (negative[i] + negative[j])
                if remain in posSet: ans.add(tuple(sorted([negative[i], negative[j], remain])))
        
        # (n, m, -n-m)
        for i in range(len(positive)):
            for j in range(i+1, len(positive)):
                remain = -1 * (positive[i] + positive[j])
                if remain in negSet: ans.add(tuple(sorted([positive[i], positive[j], remain])))
                    
        return ans
```

{% endtab %}
{% endtabs %}