// Runtime: 842 ms, faster than 5.01% of Java online submissions for 3Sum.
// Memory Usage: 48.1 MB, less than 82.68% of Java online submissions for 3Sum.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();

        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++)
            for (int j = i + 1; j < nums.length - 1; j++) {
                int bsr = Arrays.binarySearch(nums, j + 1, nums.length, -nums[i] - nums[j]);

                if (bsr >= 0) {
                    boolean needsAdding = true;
                    for (int r = 0; r < results.size(); r++) {
                        if ((results.get(r).get(0) == nums[i]) && (results.get(r).get(1) == nums[j])) {
                            needsAdding  = false;
                            break;
                        }
                    }
                    if (needsAdding) {
                        List<Integer> result = new ArrayList<Integer>();
                        result.add(nums[i]);
                        result.add(nums[j]);
                        result.add(nums[bsr]);

                        results.add(result);
                    }
                }
            }

        return results;
    }
}