**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**:

inta [] = { 3,1,7,4,5,9,10} , k = 21;Output: Elements are 7 4 10inta [] = { 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:**

public class ThreeNumbersSumKBruteForce { | |

public static void find(int [] a, int k){ | |

for (int i = 0; i <a.length ; i++) { | |

for (int j = i+1; j <a.length ; j++) { | |

for (int l = j+1; l <a.length ; l++) { | |

if(a[i]+a[j]+a[l]==k){ | |

System.out.println("Found 3 elements whose sum is = " +k); | |

System.out.println("Elements are " + a[i] + " " + a[j]+ " " + a[l]); | |

return; | |

} | |

} | |

} | |

} | |

System.out.println("Did not find 3 elements whose sum is = " +k); | |

} | |

public static void main(String[] args) { | |

int a [] = { 3,1,7,4,5,9,10}; | |

int k = 21; | |

find(a,k); | |

} | |

} |

**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:**

import java.util.Arrays; | |

public class ThreeNumbersSumKSorting { | |

public static void find(int [] a, int k){ | |

Arrays.sort(a); | |

for (int i = 0; i <a.length ; i++) { | |

int x = a[i]; | |

//now problem is reduced to find two numbers in an array whose sum = M | |

//here M = k – x and array from index = 1 to end | |

int M = k –x; | |

int start = i + 1; | |

int end = a.length–1; | |

while(start<end){ | |

int sum = a[start] + a[end]; | |

if(sum==M){ | |

System.out.println("Found 3 elements whose sum is = " +k); | |

System.out.println("Elements are " + a[i] + " " + a[start]+ " " + a[end]); | |

return; | |

}else if(sum<M) | |

start++; | |

else //sum>M | |

end—; | |

} | |

} | |

} | |

public static void main(String[] args) { | |

int a [] = { 3,1,7,4,5,9,10}; | |

int k = 21; | |

find(a,k); | |

} | |

} |

**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**:

https://gist.github.com/thmain/0ec5d9e362e610a5a66cdfde9bfbf9b0

**Output**:

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