Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Method1. DFS 有case过不了
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> clist = new ArrayList<>();
        Arrays.sort(nums);
        helper(nums, res, clist, 0);
        return res;
    }

    private void helper(int[] nums, List<List<Integer>> res, List<Integer> clist, int start) {
        if(clist.size() > 3) return;
        if(clist.size() == 3 && clist.get(0) + clist.get(1) + clist.get(2) == 0) {
            res.add(new ArrayList<>(clist));
            return;
        }

        for(int i = start; i < nums.length; i++) {
            clist.add(nums[i]);
            helper(nums, res, clist, i+1);
            clist.remove(clist.size()-1);
            while (i < nums.length-1 && nums[i+1] == nums[i]) i++;
        }
    }
}

Method2. brutal force 有case过不了
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);

        for(int i = 0; i < nums.length - 2; i++) {
            List<Integer> clist = new ArrayList<>();
            clist.add(nums[i]);
            for(int j = i+1; j < nums.length -1; j++) {
                clist.add(nums[j]);
                for(int m = j + 1; m < nums.length; m++) {
                    int sum = nums[i] + nums[j] + nums[m];
                    if(sum == 0) {
                        clist.add(nums[m]);
                        res.add(new ArrayList<>(clist));
                        clist.remove(2);
                    } else if (sum > 0) {
                        break;
                    }
                    while(m < nums.length - 1 && nums[m+1] == nums[m]) m++;
                }
                clist.remove(1);
                while(j < nums.length - 2 && nums[j+1] == nums[j]) j++;
            }
            while(i < nums.length - 3 && nums[i+1] == nums[i]) i++;
        }
        return res;
    }
}

Method3. 先拿出第一个，后两个从头从尾一对对拿
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);

        for(int i = 0; i < nums.length - 2; i++) {
            List<Integer> clist = new ArrayList<>();
            clist.add(nums[i]);
            int start = i + 1;
            int end = nums.length - 1;
            while(start < end) {
                int sum = nums[i] + nums[start] + nums[end];
                if(sum > 0) {
                    end--;
                } else if (sum < 0) {
                    start++;
                } else {
                    clist.add(nums[start]);
                    clist.add(nums[end]);
                    res.add(new ArrayList<>(clist));
                    clist.remove(2);
                    clist.remove(1);
                    start++;
                    end--;
                    while(start < end && nums[start] == nums[start-1]) start++;
                    while(start < end && nums[end] == nums[end+1]) end--;
                }
            }
            while(i < nums.length - 3 && nums[i+1] == nums[i]) i++;
        }
        return res;
    }
}