# Find all triplets in array that add up to a given sum

Posted on

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

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);
}
}
``````

GitHub

Solution

• `Triplet.hashCode()` and `Triplet.equals(Object)` are not compatible with each other. `Triplet.hashCode()` considers the order of the three integers, while `Triplet.equals(Object)` doesn’t. Judging by the complexity of your method `Triplet.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 method `hashCode()` before calculating the hash.

• In fact, `Triplet.equals(Object)` is itself broken. Consider this: If we define `Triplet a = new Triplet(1,2,3)` and `Triplet b = new Triplet(1,1,1)`, then `a.equals(b)` will return `true`, but `b.equals(a)` will return `false`.

• Regardless of the above, you are creating unnecessary `List`s in `Triplet.equals(Object)`:

``````numbers.addAll(new ArrayList<>(Arrays.asList(x, y, z)));
``````

Here, the explicit creation of an `ArrayList` from the contents of the `List` returned by the invocation of `Arrays.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 a `List`. You could even bypass the creation of an intermediate `List` 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}`, then `Set`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 a `List` and then compare the two `List`s for equality. Actually, you could already sort the integer’s in the `Triplet`‘s constructor, which would ensure that you only ever have to sort the three integers of a `Triplet` 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 is `5`, then your code will yield a non-existing triplet `[5, -5, 5]`, because it counts the integer `5` 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);
``````

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:

1. build every possible pair
2. remove duplicates
3. calculate sum
4. 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) {
}
}
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) {
}
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.