**Solution with discussion** https://discuss.leetcode.com/topic/75883/python-solution-with-detailed-explanation

**3Sum** https://leetcode.com/problems/3sum/

**Sort based algorithm**

- a+b = -c. 3SUM reduces to 2SUM problem.

**Handling Duplicates in 2SUM**

- Say index s and e are forming a solution in a sorted array. Now givens nums[s], there is a unique nums[e] such that nums[s]+nums[e]=Target. Therefore, if nums[s+1] is the same as nums[s], then searching in range s+1 to e will give us a duplicate solution. Thus we must move s till nums[s] != nums[s-1] to avoid getting duplicates.

```
while s<e and nums[s] == nums[s-1]:
s = s+1
```

**Handling Duplicates in 3SUM**

- Imagine we are at index i and we have invoked the 2SUM problem from index i+1 to end of the array. Now once the 2SUM terminates, we will have a list of all triplets which include nums[i]. To avoid duplicates, we must skip all nums[i] where nums[i] == nums[i-1].

```
if i > 0 and nums[i] == nums[i-1]:
continue
```

**Code**

```
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
N, result = len(nums), []
for i in range(N):
if i > 0 and nums[i] == nums[i-1]:
continue
target = nums[i]*-1
s,e = i+1, N-1
while s<e:
if nums[s]+nums[e] == target:
result.append([nums[i], nums[s], nums[e]])
s = s+1
while s<e and nums[s] == nums[s-1]:
s = s+1
elif nums[s] + nums[e] < target:
s = s+1
else:
e = e-1
return result
```