# All unique triplets that sum up to a given value

Given an array and a sum value, find all possible unique triplets in that array whose sum is equal to the given sum value. If no such triplets can be formed from the array, then print “No triplets can be formed”, else print all the unique triplets. For example, if the given array is {12, 3, 6, 1, 6, 9} and given sum is 24, then the unique triplets are (3, 9, 12) and (6, 6, 12) whose sum is 24.

Examples:

```Input : array = {12, 3, 6, 1, 6, 9} sum = 24
Output : [[3, 9, 12], [6, 6, 12]]

Input : array = {-2, 0, 1, 1, 2} sum = 0
Output : [[-2, 0, 2], [-2, 1, 1]]

Input : array = {-2, 0, 1, 1, 2} sum = 10
Output : No triplets can be formed
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

In a previous post, Find a triplet that sum to a given value we have discussed whether the triplets can be formed from the array or not.

Here we need to print all unique set of triplets that sum up to a given value

1. Sort the input array.
2. Find three indexes from the array i, j and k where A[i]+A[j]+A[k] = given sum value.
3. Fix the first element as A[i] and iterate i from 0 to array size – 2.
4. For each iteration of i, take j to be index of the first element in the remaining elements and k to be index of the last element.
5. Check for the triplet combination A[i]+A[j]+A[k] = given sum value.
6. If triplet is obtained (ie., A[i]+A[j]+A[k] = given sum value)
……6.1. Add all the triplet in a TreeSet with “:” separated value to get the unique triplets.
……6.2. increment the second value index
……6.3. decrement the third value index.
……6.4. repeat step 4 & 5 till j < k
7. If A[i]+A[j]+A[k] given sum value, decrement the third value index

## C++

 `// C++ program to find unique triplets ` `// that sum up to a given value. ` `#include ` `using` `namespace` `std; ` ` `  `// Structure to define a triplet. ` `struct` `triplet{ ` `    ``int` `first, second, third; ` `}; ` ` `  `// Function to find unique triplets that ` `// sum up to a given value. ` `int` `findTriplets(``int` `nums[], ``int` `n, ``int` `sum) ` `{ ` `    ``int` `i, j, k; ` `     `  `    ``// Vector to store all unique triplets. ` `    ``vector triplets; ` `     `  `    ``// Set to store already found triplets ` `    ``// to avoid duplication. ` `    ``unordered_set uniqTriplets; ` `     `  `    ``// Variable used to hold triplet  ` `    ``// converted to string form. ` `    ``string temp; ` `     `  `    ``// Variable used to store current ` `    ``// triplet which is stored in vector ` `    ``// if it is unique. ` `    ``triplet newTriplet; ` `     `  `    ``// Sort the input array. ` `    ``sort(nums, nums + n); ` `     `  `    ``// Iterate over the array from the ` `    ``// start and consider it as the  ` `    ``// first element. ` `    ``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 sum of triplet is equal to  ` `            ``// given value, then check if ` `            ``// this triplet is unique or not. ` `            ``// To check uniqueness, convert  ` `            ``// triplet to string form and ` `            ``// then check if this string is  ` `            ``// present in set or not. If  ` `            ``// triplet is unique, then store ` `            ``// it in vector. ` `            ``if``(nums[i] + nums[j] + nums[k] == sum) ` `            ``{ ` `                ``temp = to_string(nums[i]) + ``" : "`  `                     ``+ to_string(nums[j]) + ``" : "` `                             ``+ to_string(nums[k]); ` `                ``if``(uniqTriplets.find(temp) ==  ` `                                ``uniqTriplets.end()) ` `                ``{ ` `                    ``uniqTriplets.insert(temp); ` `                    ``newTriplet.first = nums[i]; ` `                    ``newTriplet.second = nums[j]; ` `                    ``newTriplet.third = nums[k]; ` `                    ``triplets.push_back(newTriplet); ` `                ``} ` `                 `  `                ``// Increment the first index  ` `                ``// and decrement the last ` `                ``// index of remaining elements. ` `                ``j++; ` `                ``k--; ` `            ``} ` `             `  `            ``// If sum is greater than given  ` `            ``// value then to reduce sum  ` `            ``// decrement the last index. ` `            ``else` `if``(nums[i] + nums[j] + ` `                                 ``nums[k] > sum) ` `                ``k--; ` `             `  `            ``// If sum is less than given value ` `            ``// then to increase sum increment  ` `            ``// the first index of remaining ` `            ``// elements. ` `            ``else` `                ``j++; ` `        ``} ` `    ``} ` `     `  `    ``// If no unique triplet is found, then ` `    ``// return 0. ` `    ``if``(triplets.size() == 0) ` `        ``return` `0; ` `     `  `    ``// Print all unique triplets stored in  ` `    ``// vector. ` `    ``for``(i = 0; i < triplets.size(); i++) ` `    ``{ ` `        ``cout << ``"["` `<< triplets[i].first  ` `            ``<< ``", "` `<< triplets[i].second ` `          ``<< ``", "` `<< triplets[i].third <<``"], "``; ` `    ``} ` `} ` ` `  `// Driver Function. ` `int` `main()  ` `{ ` `    ``int` `nums[] = { 12, 3, 6, 1, 6, 9 }; ` `    ``int` `n = ``sizeof``(nums) / ``sizeof``(nums[0]); ` `    ``int` `sum = 24; ` `    ``if``(!findTriplets(nums, n, sum)) ` `        ``cout << ``"No triplets can be formed."``; ` ` `  `    ``return` `0; ` `} ` ` `  `// This code is contributed by NIKHIL JINDAL. `

## Java

 `// Java program to find all triplets with given sum ` `import` `java.util.*; ` ` `  `public` `class` `triplets { ` ` `  `    ``// returns all triplets whose sum is equal to sum value ` `    ``public` `static` `List > findTriplets(``int``[] nums, ``int` `sum) ` `    ``{ ` ` `  `        ``/* Sort the elements */` `        ``Arrays.sort(nums); ` ` `  `        ``List > pair = ``new` `ArrayList<>(); ` `        ``TreeSet set = ``new` `TreeSet(); ` `        ``List triplets = ``new` `ArrayList<>(); ` ` `  `        ``/* Iterate over the array from the start and  ` `           ``consider it as the first element*/` `        ``for` `(``int` `i = ``0``; i < nums.length - ``2``; i++) { ` ` `  `            ``// index of the first element in the ` `            ``// remaining elements ` `            ``int` `j = i + ``1``; ` ` `  `            ``// index of the last element ` `            ``int` `k = nums.length - ``1``; ` ` `  `            ``while` `(j < k) { ` ` `  `                ``if` `(nums[i] + nums[j] + nums[k] == sum) { ` ` `  `                    ``String str = nums[i] + ``":"` `+ nums[j] + ``":"` `+ nums[k]; ` ` `  `                    ``if` `(!set.contains(str)) { ` ` `  `                        ``// To check for the unique triplet ` `                        ``triplets.add(nums[i]); ` `                        ``triplets.add(nums[j]); ` `                        ``triplets.add(nums[k]); ` `                        ``pair.add(triplets); ` `                        ``triplets = ``new` `ArrayList<>(); ` `                        ``set.add(str); ` `                    ``} ` ` `  `                    ``j++; ``// increment the second value index ` `                    ``k--; ``// decrement the third value index ` ` `  `                ``} ``else` `if` `(nums[i] + nums[j] + nums[k] < sum) ` `                    ``j++; ` ` `  `                ``else` `// nums[i] + nums[j] + nums[k] > sum ` `                    ``k--; ` `            ``} ` `        ``} ` `        ``return` `pair; ` `    ``} ` ` `  `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int``[] nums = { ``12``, ``3``, ``6``, ``1``, ``6``, ``9` `}; ` `        ``int` `sum = ``24``; ` ` `  `        ``List > triplets = findTriplets(nums, sum); ` ` `  `        ``if` `(!triplets.isEmpty()) { ` `            ``System.out.println(triplets); ` `        ``} ``else` `{ ` `            ``System.out.println(``"No triplets can be formed"``); ` `        ``} ` `    ``} ` `} `

Output:

```[[3, 9, 12], [6, 6, 12]]
```

Time Complexity: O(n2)

## tags:

Arrays Hash Searching Arrays Searching Hash