Problem
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 is24
, 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
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 time.
Here is my code:
package kata.array;
import java.util.*;
public class ThreeSum {
static class Triplet {
int x, y, z;
public Triplet(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
@Override
public int hashCode() {
return Objects.hash(x, y, z);
}
@Override
public boolean equals(Object o) {
if (o instanceof Triplet) {
Set<Integer> numbers = new HashSet<>();
numbers.addAll(new ArrayList<>(Arrays.asList(x, y, z)));
Triplet other = (Triplet) o;
return numbers.containsAll(new ArrayList<>(Arrays.asList(other.x, other.y, other.z)));
}
return false;
}
}
public static Set<Triplet> findTriplets(int numbers[], int targetSum) {
Set<Triplet> triplets = new HashSet<>();
// insert all pairs in the look up table
Map<Integer, int[]> lookup = new HashMap<>();
for (int i = 0; i < numbers.length  1; i++) {
for (int j = i + 1; j < numbers.length; j++) {
int total = numbers[i] + numbers[j];
lookup.put(total, new int[]{i, j});
}
}
// look for the complement, if found viola! here you go with the matching triplet
for (int number : numbers) {
int complement = targetSum  number;
if (lookup.containsKey(complement)) {
int indexes[] = lookup.get(complement);
int x = numbers[indexes[0]], y = numbers[indexes[1]];
triplets.add(new Triplet(x, y, number));
}
}
return triplets;
}
}
To run this code:
public void findTriplets() throws Exception {
int numbers[] = {12, 3, 4, 1, 6, 9};
System.out.print(ThreeSum.findTriplets(numbers, 24));
for (ThreeSum.Triplet triplet : ThreeSum.findTriplets(numbers, 24)) {
System.out.println(triplet.x + ", " + triplet.y + ", " + triplet.z);
}
// can handle duplicate?
System.out.println("==============================");
numbers = new int[] {12, 3, 4, 1, 6, 9, 9, 9, 9, 9};
System.out.print(ThreeSum.findTriplets(numbers, 24));
for (ThreeSum.Triplet triplet : ThreeSum.findTriplets(numbers, 24)) {
System.out.println(triplet.x + ", " + triplet.y + ", " + triplet.z);
}
}
Solution

Triplet.hashCode()
andTriplet.equals(Object)
are not compatible with each other.Triplet.hashCode()
considers the order of the three integers, whileTriplet.equals(Object)
doesn’t. Judging by the complexity of your methodTriplet.equals(Object)
, I assume that you intend the order of the integers to be disregarded. A way to accomplish this would be to sort the integers in the methodhashCode()
before calculating the hash. 
In fact,
Triplet.equals(Object)
is itself broken. Consider this: If we defineTriplet a = new Triplet(1,2,3)
andTriplet b = new Triplet(1,1,1)
, thena.equals(b)
will returntrue
, butb.equals(a)
will returnfalse
. 
Regardless of the above, you are creating unnecessary
List
s inTriplet.equals(Object)
:numbers.addAll(new ArrayList<>(Arrays.asList(x, y, z)));
Here, the explicit creation of an
ArrayList
from the contents of theList
returned by the invocation ofArrays.asList(T... a)
is redundant – the following would suffice:numbers.addAll(Arrays.asList(x, y, z));
The same applies to the process of converting the elements of
other
to aList
. You could even bypass the creation of an intermediateList
completely by using a stream:Set<Integer> numbers = Stream.of(x,y,z).collect(Collectors.toSet());
But this is not going to help you anyway, because if you have two triplets like
{1,1,2}
and{1,2,2}
, thenSet
s are useless for comparing the two triplets.The easiest way to go about it is probably, just like in the method
hashCode()
, to sort the integers from the triplets as aList
and then compare the twoList
s for equality. Actually, you could already sort the integer’s in theTriplet
‘s constructor, which would ensure that you only ever have to sort the three integers of aTriplet
once. True, this does not preserve the order of the integers, but then, this is not really necessary for the purpose of this program either. 
Your code fails in scenarios such as the following: If the input array is
{5, 5, 7}
and the target sum is5
, then your code will yield a nonexisting triplet[5, 5, 5]
, because it counts the integer5
twice.
Arrays.asList(other.x, other.y, other.z)
already returns a new list. There is no need to add the result to a new ArrayList
you could just use
numbers.containsAll(Arrays.asList(other.x, other.y, other.z));
You creating some unnecessary objects that still need to be cleaned up by the garbage collector. e.g.: this could save you some memory. Instead of:
numbers.addAll(new ArrayList<>(Arrays.asList(x, y, z)));
use
numbers.add(x);
numbers.add(y);
numbers.add(z);
Here you can save one lookup in the HashMap. Instead of:
if (lookup.containsKey(complement)) {
int indexes[] = lookup.get(complement);
...
you can write:
int indexes[] = lookup.get(complement);
if (indexes != null) {
...
Here are my 2 cents:
The reason why you came up with two different solutions is: Your mind is preset to procedural solutions an premature optimization.
A straight forward solution for the “sum of two” problem would be like this:
 build every possible pair
 remove duplicates
 calculate sum
 add to result if sum matches
The “sum of three” problem only differs in step 1. and step 3. (where step three could easily be derived to work with any number of elements).
So here is how I’d done that task:
sum of two
public class TwoSumProblemUsingBinarySearch {
public static class Pair {
private final int x;
private final int y;
public Pair(int x, int y) {
this.x = Math.min(x, y);
this.y = Math.max(x, y);
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
@Override
public boolean equals(Object other) {
if (other instanceof Pair) {
Pair o = (Pair) other;
return this.x == o.x && this.y == o.y;
}
return false;
}
@Override
public String toString() {
return String.format("(%d, %d)", x, y);
}
public boolean hasSumOf(int target) {
return target == x + y;
}
}
public static Set<Pair> findAllParis(int input[], int target) {
Set<Pair> pairs = createDistinctPairsFromInput(input);
return removePairsNotMatchingTarget(target, pairs);
}
private static Set<Pair> createDistinctPairsFromInput(int[] input) {
Set<Pair> pairs = new HashSet<>();
for (int x : input) {
for (int y : input) {
pairs.add(new Pair(x, y));
}
}
return pairs;
}
private static Set<Pair> removePairsNotMatchingTarget(int target, Set<Pair> pairs) {
return pairs.stream().filter(p > p.hasSumOf(target)).collect(Collectors.toSet());
}
}
Yes, this solution might perform awfully for large input arrays but with the given example it is fast enough.
sum of three
What do we need to change to adopt the previous solution to the “sum of two” solution to the “sum of three” problem?
 we need to change the ´Pair` class to handle 3 (or more) values
 we need to add another foreach loop in the Pair factory method
so lets first change the Pair
class:
public static class Pair {
private final List<Integer> numbers =new ArrayList<>();
public Pair(int... y) {
for (int i : y) {
numbers.add(i);
}
Collections.sort(numbers);
}
@Override
public int hashCode() {
return Objects.hash(numbers);
}
@Override
public boolean equals(Object other) {
if (other instanceof Pair) {
Pair o = (Pair) other;
return this.numbers.size() == o.numbers.size() && this.numbers.containsAll(o.numbers);
}
return false;
}
@Override
public String toString() {
return String.format("(%s)", numbers.stream()
.map(i > i.toString())
.collect(Collectors.joining(", ")));
}
public boolean hasSumOf(int target) {
return target == numbers.stream().mapToInt(i>i).sum();
}
}
This still passes your test case for the “sum of two” problem.
And now we change the Pair
creation method to adopt the new requirement:
private static Set<Pair> createDistinctPairsFromInput(int[] input) {
Set<Pair> pairs = new HashSet<>();
for (int x : input) {
for (int y : input) {
for (int z : input) {
pairs.add(new Pair(x, y, z));
}
}
}
return pairs;
}
Now we have a similar solution for a similar problem. We could even go further and transform the factory method for the Pairs to be parameterized so that the same solution could be used for all “find combinations with matching sum” problems.
conclusion
My approach is totally focused on the problem. No optimization or “clever tricks” have been used. That allowed me to easily extend the first approach to a more general version to handle similar problems.