## Table of Contents

The Three Sum problem is a well-known problem in computer science that involves finding all unique triplets in an array of integers that add up to a target sum.

For example, given the array `[1, 2, 3, 4, 5, 6, 7]`

and a target sum of `10`

, the solution would be `[[1, 2, 7], [1, 3, 6], [1, 4, 5], [2, 3, 5]]`

, as these are the unique combinations of three integers that add up to `10`

.

The pseudocode for solving this problem using a brute-force approach is as follows:

```
function threeSum(nums, target):
result = []
n = length(nums)
for i from 0 to n-3:
for j from i+1 to n-2:
for k from j+1 to n-1:
if nums[i] + nums[j] + nums[k] == target:
triplet = [nums[i], nums[j], nums[k]]
triplet.sort()
if triplet not in result:
result.append(triplet)
return result
```

This pseudocode has a time complexity of O(n^3) since it requires three nested loops to iterate over all possible triplets. A more efficient solution can be achieved using a two-pointer approach, which has a time complexity of O(n^2).

there are several efficient approaches to solve the Three Sum problem. I’ll provide pseudocode for two more approaches: one that uses the Two Sum problem as a helper function and another that uses a sorting-based approach.

## Approach 2: Two Sum Approach

This approach uses the Two Sum problem as a helper function to solve the Three Sum problem. For each element `num`

in the input array, we use the Two Sum function to find a pair of numbers that add up to `target - num`

.

We add `num`

to the pair to form a triplet that adds up to the target sum. Since the Two Sum function is linear time, this approach has a time complexity of O(n^2).

```
function threeSum(nums, target):
result = []
n = len(nums)
nums.sort()
for i from 0 to n-3:
if i > 0 and nums[i] == nums[i-1]:
continue
left = i+1
right = n-1
while left < right:
curr_sum = nums[i] + nums[left] + nums[right]
if curr_sum == target:
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left-1]:
left += 1
while left < right and nums[right] == nums[right+1]:
right -= 1
elif curr_sum < target:
left += 1
else:
right -= 1
return result
```

In this approach, we first sort the input array to make it easier to find duplicates and to use the Two Sum function. We then iterate over the array, skipping duplicates, and for each element, we use the Two Sum function to find a pair of numbers that add up to the target sum minus the current element.

We add the current element to the pair to form a triplet that adds up to the target sum. We also use two pointers to keep track of the left and right ends of the array, and we move them accordingly to find all possible triplets.

## Approach 3: Sorting Approach

This approach involves sorting the input array and using two pointers to find all possible triplets that add up to the target sum. We first sort the input array and then iterate over it, skipping duplicates.

For each element `num`

in the array, we use two pointers, one that starts at the next element `left`

and another that starts at the last element `right`

. We then move the pointers inward, checking the sum of the current triplet against the target sum.

If the sum is less than the target sum, we increment the `left`

pointer. If the sum is greater than the target sum, we decrement the `right`

pointer. If the sum is equal to the target sum, we add the triplet to our results and skip any duplicates of `left`

and `right`

.

This approach has a time complexity of O(n^2) since we iterate over the array only once and use two pointers to find all possible triplets.

```
function threeSum(nums, target):
result = []
n = len(nums)
nums.sort()
for i from 0 to n-3:
if i > 0 and nums[i] == nums[i-1]:
continue
left = i+1
right = n-1
while left < right:
curr_sum = nums[i] + nums[left] + nums[right]
if curr_sum == target:
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left-1]:
left += 1
while left < right and nums[right] == nums[right+1]:
right -= 1
elif curr_sum < target:
left += 1
else:
right -= 1
return result
```

In this approach, we also sort the input array and iterate over it, skipping duplicates. We then use two pointers, `left` and `right`, to move inward from opposite ends of the array.

We compare the sum of the current triplet with the target sum, and move the pointers accordingly to find all possible triplets. We also skip any duplicates of `left` and `right` to avoid adding duplicate triplets to our result.

Both of these approaches are more efficient than the brute-force approach I mentioned earlier, with the sorting-based approach being the most efficient with a time complexity of O(n^2).

The sorting-based approach is better than the Two Sum approach in terms of time complexity. The sorting-based approach has a time complexity of O(n^2) while the Two Sum approach has a time complexity of O(n^2 log n).

This is because the sorting-based approach requires only two nested loops and the use of two pointers, while the Two Sum approach requires the use of the Two Sum function, which itself has a time complexity of O(n log n), and an additional loop.

However, the Two Sum approach is more space-efficient than the sorting-based approach. The Two Sum approach requires only a constant amount of extra space for variables, while the sorting-based approach requires extra space for sorting the input array.

## Three Sum : Java Solution

```
import java.util.*;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int target = -nums[i];
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
}
```

In this Java implementation, we first sort the input array to make it easier to find duplicates and use the Two Sum approach.

We then iterate over the array, skipping duplicates, and for each element `num`

in the array, we use two pointers, one that starts at the next element `left`

and another that starts at the last element `right`

.

We then move the pointers inward, checking the sum of the current triplet against the target sum. If the sum is less than the target sum, we increment the `left`

pointer.

If the sum is greater than the target sum, we decrement the `right`

pointer. If the sum is equal to the target sum, we add the triplet to our results and skip any duplicates of `left`

and `right`

.

## Three Sum : JavaScript Solution

```
var threeSum = function(nums) {
let result = [];
nums.sort((a, b) => a - b);
let n = nums.length;
for (let i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let target = -nums[i];
let left = i + 1;
let right = n - 1;
while (left < right) {
let sum = nums[left] + nums[right];
if (sum === target) {
result.push([nums[i], nums[left], nums[right]]);
left++;
right--;
while (left < right && nums[left] === nums[left - 1]) left++;
while (left < right && nums[right] === nums[right + 1]) right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
};
```

In this JavaScript implementation, we also sort the input array and iterate over it, skipping duplicates.

We use two pointers, `left`

and `right`

, to move inward from opposite ends of the array. We compare the sum of the current triplet with the target sum, and move the pointers accordingly to find all possible triplets.

We also skip any duplicates of `left`

and `right`

to avoid adding duplicate triplets to our result.

## Three Sum : Python Solution

```
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort()
n = len(nums)
for i in range(n-2):
if i > 0 and nums[i] == nums[i-1]:
continue
target = -nums[i]
left = i+1
right = n-1
while left < right:
curr_sum = nums[left] + nums[right]
if curr_sum == target:
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left-1]:
left += 1
while left < right and nums[right] == nums[right+1]:
right -= 1
elif curr_sum < target:
left += 1
else:
right -= 1
return result
```

In this Python implementation, we use a similar approach as in the Java and JavaScript implementations.

We sort the input array, iterate over it, and use two pointers to find all possible triplets that add up to the target sum.

We also skip duplicates and move the pointers accordingly to avoid adding duplicate triplets to our result.

## Three Sum : Ruby Solution

```
def three_sum(nums)
result = []
nums.sort!
n = nums.length
for i in 0..n-3 do
next if i > 0 && nums[i] == nums[i-1]
target = -nums[i]
left = i+1
right = n-1
while left < right do
curr_sum = nums[left] + nums[right]
if curr_sum == target
result << [nums[i], nums[left], nums[right]]
left += 1
right -= 1
left += 1 while left < right && nums[left] == nums[left-1]
right -= 1 while left < right && nums[right] == nums[right+1]
elsif curr_sum < target
left += 1
else
right -= 1
end
end
end
result
end
```

In this Ruby implementation, we also sort the input array and use two pointers to find all possible triplets that add up to the target sum.

We skip duplicates and move the pointers accordingly to avoid adding duplicate triplets to our result.