**Objective**: Given an array of integer write an algorithm to find 3 elements that sum to a given number k. In short a+b+c = k.

**Example**:

**int **a [] = { 3,1,7,4,5,9,10} , k = 21;Output: Elements are 7 4 10 **int **a [] = { 3,1,7,4,5,9,10} , k = 55;Output: **Did not find 3 elements whose sum is 55**** **

**Approach: Brute Force**

Use 3 nested loops and find the 3 elements which sum to k.

Time Complexity: O(n^3)

**Code:**

**Approach: Sorting**

- Sort the array.
- Use the other loop to fix the one element at a time
- Now problem is reduced to “Find a pair of numbers from an array whose sum equals k”

Time Complexity: O(n^2)

**Code:**

**Approach: Use Hashing**

- Use the other loop to fix the one element at a time.
- Now required_sum is (with two elements) = k-fixed element.
- Create a HashSet, Iterate through rest of the array.
- For current_element, remain_value = required_sum – current_element.
- Check if remain_value in the HashSet, we have found our triplets else add current_element to the hashset.

Time Complexity: O(n^2)

**Code**:

**Output**:

Found 3 elements whose sum is = 22
Elements are 3 10 9

__________________________________________________

**Top Companies Interview Questions..-**

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

__________________________________________________

### Like this:

Like Loading...

*Related*