class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);

        Set<List<Integer>> results = new HashSet<>(); // use Set to remove duplicate element

        Map<Integer, Integer> val_index = new HashMap<>();

        // fix the first number
        for (int i = 0; i < nums.length ;i++) {
            int num = nums[i];
            int num_target = 0 - (num);

            for (int j = i; j < nums.length ;j++) {
                if (j == i) continue;

                int num_second = nums[j];
                int num_third_target = num_target - num_second;

                // check if exist
                Integer i_num_third = val_index.get(num_third_target);
                if (i_num_third != null) {
                    if (i_num_third == i || i_num_third == j) continue;

                    // collect it
                    add(nums, results, i, j, i_num_third); // TODO

                }

                val_index.put(num_second, j);

            }

        } // end of if

        List<List<Integer>> results_list = new ArrayList<>(results);
        return results_list;

    }

    public void add(int[] nums, Set<List<Integer>> results, int i, int j, int k) {

        Integer[] array = new Integer[3];
        array[0] = nums[i];
        array[1] = nums[j];
        array[2] = nums[k];

        Arrays.sort(array); // make sure no duplicate witth varying orders are added

        results.add(Arrays.asList(array));
    }

}