class Solution {
    List<Integer> sort(int a, int b, int c) {
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        if (a > c) {
            int temp = a;
            a = c;
            c = temp;
        }
        if (b > c) {
            int temp = b;
            b = c;
            c = temp;
        }
        return Arrays.asList(a, b, c);
    }

    boolean isUniqueIndex(Set<Integer> indices, int index1, int index2) {
        if (indices.contains(index1) && indices.contains(index2)) {
            return indices.size() > 2;
        }
        if (indices.contains(index1) || indices.contains(index2)) {
            return indices.size() > 1;
        }
        return indices.size() > 0;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> solutions = new HashSet<>();
        Map<Integer, Set<Integer>> numToIndices = new HashMap<>();

        // Fill out the map
        for (int i=0; i<nums.length; ++i) {
            int num = nums[i];
            if (!numToIndices.containsKey(num)) {
                numToIndices.put(num, new HashSet<>());
            }
            numToIndices.get(num).add(i);
        }

        // Check for tiples
        for (int i=0; i<nums.length; ++i) {
            for (int j=i+1; j<nums.length; ++j) {
                int first = nums[i];
                int second = nums[j];
                int third = -(first + second);
                // Potential solution
                if (numToIndices.containsKey(third)) {
                    if (isUniqueIndex(numToIndices.get(third), i, j)) {
                        // Tuple is unique indices
                        solutions.add(sort(first, second, third));
                    }
                }
            }
        }

        List<List<Integer>> toReturn = new ArrayList<>();
        toReturn.addAll(solutions);
        return toReturn;
   }
}