# Three sum using binary search

Given an array and a value, find all the triplets in the array whose sum is equal to the given value. For example, if the given array is {12, 3, 4, 1, 6, 9} and the given sum is 24, then this is one triplet (12, 3 and 9) which contributes to the total sum of 24.

Solution for given example:

6, 9, 9

6, 6, 12

3, 9, 12

Conditions:

• The ordering of the numbers in the solution does not matter.

• Duplicate triplet is not allowed.

• A number is not allowed to be used multiple times.

A similar question was asked here, though it was HashMap-based.

Github

public class ThreeSumUsingBinarySearch {

static class Triplet {
final List<Integer> triplets;

public Triplet(int x, int y, int z) {
triplets = Arrays.asList(x, y, z);
Collections.sort(triplets);
}

@Override
public String toString() {
return String.format("(%d,%d,%d)", triplets.get(0), triplets.get(1), triplets.get(2));
}

@Override
public int hashCode() {
return triplets.hashCode();
}

@Override
public boolean equals(Object o) {
if (o instanceof Triplet) {

Triplet other = (Triplet) o;
return other.triplets.equals(this.triplets);
}

return false;
}
}

public static Set<Triplet> findTriplets(int array[], int targetSum) {

int[] numbers = Arrays.copyOf(array, array.length);
Set<Triplet> triplets = new HashSet<>();

Arrays.sort(numbers);

for (int i = 0; i < array.length; i++) {
int complement = targetSum - numbers[i];

for (int low = i + 1, high = numbers.length - 1; low < high; ) {
int total = numbers[low] + numbers[high];

if (total < complement) {
low++;
} else if (total > complement) {
high--;
} else {
// found the match
low++;
high--;
}
}
}

return triplets;
}
}

• Just a small note as I have just noticed the "interview-questions" tag: if I were the interviewer, the most convincing solution for me would be to know that there's a library "apache-commons-math3" which contains CombinatoricsUtils that readily gives you a "choose k from n"-iterator. Using this iterator to create the index lookups, the whole thing basically becomes a one-liner. The best (professional) code is normally the one, that you do not need to write and maintain. ;-)
– mtj
Mar 27 '18 at 11:54
• @mtj thats a good point - however, in an interview setting solving them optimally is even more important as that clearly illustrates an engineers problem solving ability and critical thinking. Mar 27 '18 at 15:02
• You state that "A number is not allowed to be used multiple times" yet your solutions show numbers being used twice Jul 4 '18 at 20:46