**Introduction**

This blog will discuss the approach to finding all the unique triplets that sum up to a given value. Before jumping on the approach to the problem, let us first understand the problem.

**Problem Statement**

Given an array, we have to find and print all the unique triplets whose sum equals the given value. Note that all the triplets should be unique. In case no such triplets are possible, return an empty array.

For example, (3,5,5) and (5,3,5) should be considered the same, and only one should be returned.

**Sample Example **

**Input : **array = {15,5,10,5,10} sum = 25

**Output : **[ [15,5,5], [5,10,5] ]

Since 15 + 5 + 5 = 25 and 5 + 10 + 5 = 25, therefore the unique triplets are [15,5,5] and [5,10,5].

**Input : **array = {-3,0,2,3,-2} sum = 0

**Output : **[ [-3,0,3], [2,0,-2] ]

Since 0 + 2 + (-2) = 0 and (-3) + 0 + 3 = 0, therefore the unique triplets are [-3,0,3] and [2,0,-2].

**Brute Force Approach**

In this approach,we basically need to find three indexes which satisfy the condition A[i] + A[j] + A[k] = given sum. We do this by fixing the first index and iterating the other two indexes as a two-pointer system. In order to maintain the uniqueness of the triplets, a set will be used.

**Algorithm**

Step 1: Sort the input array

Step 2: Find three index i,j,k such that A[i]+A[j]+A[k] = sum given

Step 3: Fix the first index i and let i iterate from 0 to array size - 2.

Step 4: For each iteration of i, take j to be the index of the middle element and k to be the index of the last element.

Step 5: check the following equation, A[i] + A[j] + A[k] = given sum.

Step 6: If the above equation is satisfied,then

- Add the triplet in the set
- Increment the mid index
- Decrement the third index
- Repeat step 4 & 5 till j < k

Step 7: Else if,A[i] + A[j] + A[k] > given sum, Increment the mid index.

Else, if A[i] + A[j] + A[k] < the given sum,Decrement the last index.

**Implementation**

**C++**

```
using namespace std;
// Structure to define a triplet.
struct triplet
{
int first, second, third;
};
vector<triplet> findTriplets(int nums[], int n, int sum)
{
int i, j, k;
// Vector to store all unique triplets.
vector<triplet> triplets;
//unordered Set to store already found triplets
// to avoid duplication.
unordered_set<string> uniqueTriplets;
// Variable used to hold triplet
// converted to string form.
string temp;
triplet newTriplet;
sort(nums, nums + n);
for (i = 0; i < n - 2; i++)
{
// index of the first element in
// the remaining elements.
j = i + 1;
// index of the last element.
k = n - 1;
while (j < k) {
if (nums[i] + nums[j] + nums[k] == sum)
{
temp = to_string(nums[i]) + " : "
+ to_string(nums[j]) + " : "
+ to_string(nums[k]);
if (uniqueTriplets.find(temp)
== uniqueTriplets.end()) {
uniqueTriplets.insert(temp);
newTriplet.first = nums[i];
newTriplet.second = nums[j];
newTriplet.third = nums[k];
triplets.push_back(newTriplet);
}
j++;
k--;
}
else if (nums[i] + nums[j] + nums[k] > sum)
k--;
else
j++;
}
}
return triplets;
}
// Driver Code
int main()
{
int nums[] = {15,5,10,5,10};
int n = sizeof(nums) / sizeof(nums[0]);
int sum = 25;
// Function call
vector<triplet> result = findTriplets(nums, n, sum))
if( result.size() == 0 )
cout<<”No such triplet possible”<<endl;
// Print all unique triplets stored in
// vector.
for (i = 0; i < result.size(); i++) {
cout << "[" << result[i].first << ", "
<< result[i].second << ", "
<< result[i].third << "], ";
}
return 0;
}
```

**Output : **

`[ [ 15,5,5 ],[ 5,10,10 ] ]`

**Complexity Analysis**

**Time complexity: **O( n^2 )

Since there are n traversals in total and each traversal costs O(n) time,therefore total time required would be of order O(n^2).

**Space complexity: **O( n )

As an unordered set is used therefore space complexity is of order O(n).

Also see, __Rabin Karp Algorithm__