# 3-Sum Problem
<https://leetcode.com/problems/3sum> extended version of [[2-sum]].
## "Enlightened" Brute Force
```python
table = defaultdict(list)
for i, x in enumerate(nums):
for j, y in enumerate(nums[i + 1:]):
j = j + i + 1
table[x + y].append((i, j))
result = set()
for k, z in enumerate(nums):
for i, j in table[-z]:
if j < k:
result.add(tuple(sorted([nums[i], nums[j], z])))
return list(result)
```
Still takes too long!
## [[2-pointer|Two-Pointer]]
- Use sorting and iteration to ensure that duplicates (both in terms of indices
and values) are avoided.
- Two-pointer utilized the extra information that the sum is fixed. We may
utilize the tricks in [[2-sum]] to further speed up. Alternatively, instead of
a linear search, do a [[binary-search]] instead.
- Make sure all the info are used in your solution! In this case, we ensured no
duplicate indices my enforcing that `i < j < k`.
> [!warning] Don't Go Too Far
> Declarative and Pythonic programming is great, but
> procedural programming gives you control over details in each step of the
> iteration!
[[2-pointer]]
```python
nums.sort() # step 1: sort the array
result = []
n = len(nums)
for i in range(n):
# skip duplicate elements to avoid duplicate triplets
if i > 0 and nums[i] == nums[i-1]:
continue
# use two-pointer technique to find the remaining two elements
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
# Skip duplicate elements
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
```