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

Question

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

Answer 1

• 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 Lists 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 Sets 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 Lists 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.

Answer 2

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) {
    ...

Answer 3

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) {
                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.