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
                    triplets.add(new Triplet(numbers[i], numbers[low], numbers[high]));
                    low++;
                    high--;
                }
            }
        }

        return triplets;
    }
}