# Find Triplets with Given Sum in an Unsorted Array

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] equals to a target sum

Notice that the solution set must not contain duplicate triplets.

Example 1

• Input: nums = [-1, 0, 1, 2, -1, -4], target = 0
• Output: [[-1,-1,2],[-1,0,1]]
• Explanation: The values in each solution set sum up to 0

Example 2

• Input: nums = [0, 1, 1, 2, -1, 3], target = 4
• Output: [[-1,2,3],[0,1,3],[1,1,2]]
• Explanation: The values in each solution set sum up to 4

## Approach 1: Brute Force

### Idea

The idea is to simply run three loops and check for the target sum. To avoid duplicates, we will insert the values into a set.

### Implementation

vector<vector<int>> threeSum(vector<int>& nums, const int target) {
int n = nums.size();
sort(nums.begin(), nums.end());
set<vector<int>> tripletValues;

for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
if (nums[i] + nums[j] + nums[k] == target) {
tripletValues.insert({nums[i], nums[j], nums[k]});
}
}
}
}

return vector<vector<int>>(tripletValues.begin(), tripletValues.end());
}

### Complexity Analysis

• Time Complexity: $O(N^3 + N^3log(N^3)) = O(N^3logN)$ since we are running three nested loops. Inserting the results into the set takes logarithmic time.
• Space Complexity: $O(N^3)$ extra for the set.

## Approach 2: Sort and Two Pointers

This problem can be reduced to two sum. First sort the array and then let us fix one number to nums[i] and find for pairs of sum target - nums[i] for the subarray nums[i + 1...n - 1]. The last part can be solved using the two pointers approach of two sum (approach 3 of the problem two sum).

### Implementation

vector<vector<int>> threeSum(vector<int>& nums, const int target) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> triplets;
for (int i = 0; i < n; ++i) {
// nums[i] != nums[i - 1] is used to ignore the duplicate solutions
if (i == 0 or nums[i] != nums[i - 1]) {
int cur = nums[i];
int required = target - cur;

int left = i + 1, right = n - 1;

// this part is equivalent to two sum
while (left < right) {
int curSum = nums[left] + nums[right];
if (curSum == required) {
triplets.push_back({nums[i], nums[left], nums[right]});
while(left < right and nums[right] == nums[right - 1]) --right;
while(left < right and nums[left] == nums[left + 1]) ++left;
--right;
++left;
} else if (curSum > required) {
--right;
} else {
++left;
}
}
}
}
return triplets;
}

## Complexity Analysis

• Time Complexity: $O(N^2)$\$ for the outer for and inner while loop.
• Space Complexity: $O(1)$ extra. No extra space is required.