4Sum

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:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• 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)

 solution:
 Similar to other N-Sum questions. 
 Iterate the first two elements, and use two pointers for the third  and fourth elements. 
 Tips: sort the array first. 
 Time complexity: left-right pointers can reduce O(n^2) to O(n). So its overall time complexity is  O(n^3).

public class Solution {
    public ArrayList> fourSum(int[] num, int target) {
        Arrays.sort(num);
        ArrayList> result = new ArrayList>();
        int len = num.length;
        if(len < 4) 
            return result;
            
        for(int i = 0; i <= len-4; i++){
            for(int j = i+1; j <= len-3; j++){
                int l = j + 1;
                int r = len - 1;
                while(l < r){
                    int s = num[i] + num[j] + num[l] + num[r];
                    if(s == target){
                        ArrayList tmp = new ArrayList();
                        tmp.add(num[i]);
                        tmp.add(num[j]);
                        tmp.add(num[l]);
                        tmp.add(num[r]);
                        result.add(tmp);
                        l++;
                        r--;
                    }
                    else if(s < target){
                        l++;
                    }
                    else{
                        r--;
                    }
                }
            }
        }
        
        // get rid of duplicates
        HashSet> set = new HashSet>();
        set.addAll(result);
        result.clear();
        result.addAll(set);
        
        return result;
    }
}