# Given an integer array nums, return all the triplets

3Sum

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.

Example 1:

```Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
```

Example 2:

```Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
```

Example 3:

```Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
```

Constraints:

• `3 <= nums.length <= 3000`
• `-105 <= nums[i] <= 105`

If you want to solve the `threeSum` problem with a time complexity of O(n3)O(n^3)O(n3), you can use a straightforward brute-force approach. This method involves three nested loops to check all possible triplets in the array. While this approach is less efficient than the two-pointer method, it still works correctly for finding all unique triplets that sum to zero.

### Swift Implementation:

Here’s the brute-force approach for the `threeSum` function in Swift:

``````func threeSum(_ nums: [Int]) -> [[Int]] {
var result = [[Int]]()
let n = nums.count

// Use a set to avoid duplicate triplets
var tripletSet = Set<[Int]>()

// Sort the array to help with duplicate removal
let sortedNums = nums.sorted()

for i in 0..<n {
for j in i+1..<n {
for k in j+1..<n {
if sortedNums[i] + sortedNums[j] + sortedNums[k] == 0 {
let triplet = [sortedNums[i], sortedNums[j], sortedNums[k]]
tripletSet.insert(triplet)
}
}
}
}

result = Array(tripletSet)
return result
}

// Example usage:
let nums = [-1, 0, 1, 2, -1, -4]
let triplets = threeSum(nums)
print(triplets) // Output: [[-1, -1, 2], [-1, 0, 1]]
``````

### Explanation:

1. Sorting:
• First, sort the array to help with duplicate removal later.
2. Three Nested Loops:
• Use three nested loops to iterate through all possible triplets in the array.
• The outer loop runs from `0` to `n-1`.
• The middle loop runs from `i+1` to `n-1`.
• The inner loop runs from `j+1` to `n-1`.
3. Check for Sum:
• For each triplet `(sortedNums[i], sortedNums[j], sortedNums[k])`, check if their sum is zero.
• If the sum is zero, add the triplet to a set to avoid duplicates.
4. Convert Set to Array:
• Convert the set of triplets back to an array and return it as the result.

### Time Complexity:

• This approach has a time complexity of O(n3)O(n^3)O(n3) due to the three nested loops.

### Example:

For the input `[-1, 0, 1, 2, -1, -4]`, the output will be:

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

## 2 Solution

To solve the problem of finding all unique triplets in an array that sum up to zero, we can use a sorted array and a two-pointer technique. This approach ensures that we efficiently find the triplets without duplicates. Here’s a detailed step-by-step solution:

### Approach:

1. Sort the Array:
• Sorting helps to easily skip duplicates and efficiently use the two-pointer technique.
2. Iterate Through the Array:
• Use a for loop to fix the first element of the triplet.
3. Two-Pointer Technique:
• For each fixed element, use two pointers to find pairs that sum up to the negative value of the fixed element.
4. Skip Duplicates:
• Ensure that the solution does not include duplicate triplets by skipping identical elements during the iteration.

### Implementation in Swift:

``````func threeSum(_ nums: [Int]) -> [[Int]] {
var result = [[Int]]()
let nums = nums.sorted()
let n = nums.count

for i in 0..<n {
if i > 0 && nums[i] == nums[i - 1] {
continue // Skip duplicate elements
}

var left = i + 1
var right = n - 1

while left < right {
let sum = nums[i] + nums[left] + nums[right]

if sum == 0 {
result.append([nums[i], nums[left], nums[right]])

// Skip duplicates for the second and third elements
while left < right && nums[left] == nums[left + 1] {
left += 1
}
while left < right && nums[right] == nums[right - 1] {
right -= 1
}

left += 1
right -= 1
} else if sum < 0 {
left += 1
} else {
right -= 1
}
}
}

return result
}

// Example usage:
let nums = [-1, 0, 1, 2, -1, -4]
let triplets = threeSum(nums)
print(triplets) // Output: [[-1, -1, 2], [-1, 0, 1]]
``````

### Explanation:

1. Sorting:
• First, sort the array to handle duplicates and use the two-pointer technique efficiently.
2. Main Loop:
• Iterate through the array with index `i` to fix the first element of the triplet.
• Skip duplicate elements to avoid repeating the same triplet.
3. Two-Pointer Technique:
• Initialize two pointers, `left` and `right`, for each fixed element.
• Adjust the pointers based on the sum of the triplet:
• If the sum is zero, add the triplet to the result and move both pointers inward, skipping duplicates.
• If the sum is less than zero, move the left pointer to the right to increase the sum.
• If the sum is greater than zero, move the right pointer to the left to decrease the sum.
4. Result:
• The `result` array contains all unique triplets that sum up to zero.

### Time Complexity:

• The time complexity is O(n2)O(n^2)O(n2) because we iterate through the array and use two pointers for each element. Sorting the array takes O(nlog⁡n)O(n \log n)O(nlogn).
``````func threeSum(_ nums: [Int]) -> [[Int]] {
let sortedNums = nums.sorted()
var triplets: Set<[Int]> = []

for i in 0..<sortedNums.count {
var j = i + 1
var k = sortedNums.count - 1

while j < k {
let sum = sortedNums[i] + sortedNums[j] + sortedNums[k]

if sum == 0 { triplets.insert([sortedNums[i], sortedNums[j], sortedNums[k]]) }

if sum <= 0 { j += 1 }
if sum >= 0 { k -= 1 }
}
}

return Array(triplets)
}``````