4SUM

Question

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Analysis

The idea is similar to 3SUM or 2SUM.

Pick up the first two element and find the remaining two element using binary search.

Solution

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        if(nums==null || nums.length<4) return result;
        List<Integer> tmp=new ArrayList<Integer>();
        Arrays.sort(nums);
        for(int i=0;i<=nums.length-4;i++){
            if(i==0 || nums[i]!=nums[i-1]){
                tmp.add(nums[i]);
                for(int j=i+1;j<=nums.length-3;j++){
                    if(j==i+1 || nums[j]!=nums[j-1]){
                        tmp.add(nums[j]);
                        search(nums,j+1,target-nums[i]-nums[j],tmp,result);
                        tmp.remove(tmp.size()-1);
                    }
                }
                tmp.remove(tmp.size()-1);
            }
        }
        return result;
    }

    public void search(int[] nums, int startIndex, int partialTarget, List<Integer> tmp, List<List<Integer>> result){
        int lo=startIndex, hi=nums.length-1;
        while(lo<hi){
            int lohi=nums[lo]+nums[hi];
            if(lohi==partialTarget){
                List<Integer> list=new ArrayList<Integer>(tmp);
                list.add(nums[lo]);
                list.add(nums[hi]);
                result.add(list);
                lo++;
                hi--;
                while(lo<nums.length-1 && nums[lo]==nums[lo-1]) lo++;
                while(hi>startIndex && nums[hi]==nums[hi+1])    hi--;
            }else if(lohi>partialTarget) hi--;
                  else                   lo++;   
        }
    }