18. 4Sum

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        if(nums.length <4)
            return results;
            
        Arrays.sort(nums);
        if(nums[nums.length - 1]+nums[nums.length - 2]+nums[nums.length - 3]+nums[nums.length - 4]<target) 
            return results;
            
        for(int first = 0;first<nums.length-3;++first)
        {
            if(first > 0 && nums[first]==nums[first-1])
                continue;
            if(target < nums[first]+nums[first+1]+nums[first+2]+nums[first+3])
                break;
            if(target>=0 && nums[first]>target)
                break;
            List<List<Integer>> _3SumResults = threeSum(nums, first+1, target-nums[first]);
            if(_3SumResults.size() > 0)
            {
                for(List<Integer> _3SumResult: _3SumResults)
                {
                    List<Integer> result = new ArrayList<Integer>(4);
                    result.add(nums[first]);
                    result.addAll(_3SumResult);
                    results.add(result);
                }
            }
        }
        
        return results;
    }
    
    public List<List<Integer>> threeSum(int[] num, int start, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(num[num.length - 1]+num[num.length - 2]+num[num.length - 3]<target) 
            return result;
            
        for(int first = start;first<num.length-2;++first)
        {
            if(first > start && num[first]==num[first-1])
                continue;
            if(target<num[start]+num[start+1]+num[start+2])
                break;
            if(target>=0 && num[first]>target)
                break;
            int twoSumTarget = target - num[first];
            int second = first+1;
            int third = num.length -1;
            
            while(second<third)
            {
                int sum = num[second]+num[third]; 
                if(sum == twoSumTarget)
                {
                    List<Integer> l = new ArrayList<Integer>();
                    l.add(num[first]);
                    l.add(num[second]);
                    l.add(num[third]);
                    result.add(l);
                    while(++second<third && num[second]==num[second-1]);
                    while(second<--third && num[third]==num[third+1]);
                }
                else if(sum>twoSumTarget)
                    while(second<--third && num[third]==num[third+1]);
                else 
                    while(++second<third && num[second]==num[second-1]);
            }
            
        }
        
        return result;
    }
}