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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

import java.util.HashSet; | |

public class ThreeNumbersSumKHashing { | |

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

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 remainSum = k – x and array from index = 1 to end | |

int M = k – x; | |

int start = i + 1; | |

int end = a.length – 1; | |

HashSet<Integer> map = new HashSet<>(); //assume all array elements are less than 99999 | |

for (int j=start; j<=end; j++) { | |

int remain = M–a[j]; | |

// checking for condition | |

if (remain>=0 && map.contains(remain)==true) { | |

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

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

return; | |

} | |

map.add(a[j]); | |

} | |

} | |

} | |

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

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

int k = 22; | |

find(a,k); | |

} | |

} |

**Output**:

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