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) 

Naive Way:  Use O(n^2) space list to store all 2sum Nodes. Use a map to map a 2sum to its corresponding index in 2sum list. go through each pair again to find valid four sum pairs.

 public class Solution {  
   class TwoSum{  
     int child1, child2;  
     int val;  
     TwoSum(int v, int c1, int c2){  
       this.val = v;  
       this.child1 = c1;  
       this.child2 = c2;  
     }  
   }  
   public List<List<Integer>> fourSum(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     List<TwoSum> twoSums = new ArrayList<TwoSum>();  
     Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
     // edge case  
     if(num.length < 4) return rslt;  
     // construct two sum list  
     for(int i = 0;i < num.length-1;i++)  
       for(int j = i+1;j < num.length;j++)  
         twoSums.add(new TwoSum(num[i]+num[j], i, j));  
     // sort two sum list  
     Comparator<TwoSum> comparator= new Comparator<TwoSum>(){  
       public int compare(TwoSum a, TwoSum b){  
         return a.val > b.val?1:(a.val < b.val?-1:0);  
       }  
     };  
     Collections.sort(twoSums, comparator);  
     // map two sum value with corresponding begin index in two sum list  
     int cur = 0;  
     map.put(twoSums.get(cur).val, cur);  
     for(int i = 1;i < twoSums.size();i++){  
       if(twoSums.get(i).val==twoSums.get(cur).val) continue;  
       cur = i;  
       map.put(twoSums.get(i).val, cur);  
     }  
     // find four sum  
     for(int i = 0;i < num.length-1;i++){  
       for(int j = i+1;j < num.length;j++){  
         int rest = target - num[i] - num[j];  
         if(map.containsKey(rest)){  
           int u = map.get(rest);  
           while(u < twoSums.size() && twoSums.get(u).val == rest){  
             int a = i, b = j, c = twoSums.get(u).child1, d = twoSums.get(u).child2;  
             if(a!=b && a!=c && a!=d && b!=c && b!=d && c!= d){  
               List<Integer> list = new ArrayList<Integer>();  
               list.add(num[a]);  
               list.add(num[b]);  
               list.add(num[c]);  
               list.add(num[d]);  
               Collections.sort(list);  
               set.add(list);  
             }  
             u++;  
           }  
         }  
       }  
     }  
     rslt.addAll(set);  
     return rslt;  
   }  
 }  

This is a pretty inefficient way. It doesn't quite take use of sorting.

If I get two sums as a list of number, can I apply finding two sum on that O(n^2) list using two pointer trick? It fails on the case when two sum sequence is [-4, -4, 4, 4] with target 0. Because both -4 needs to be matched with either 4 once. I cannot simply skip it after use a two sum number.

Can I sort the array first. And then, keep two pointers at begin and end. Each time, go through [begin, end] using two pointer trick like 3sum?

 public class Solution {  
   public List<List<Integer>> fourSum(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Arrays.sort(num);  
     for(int i = 0;i < num.length-3;i++){  
       if(i==0 || i> 0 && num[i]!=num[i-1]){  
       for(int j = i+1;j < num.length-2;j++){  
         if(j==i+1 || j > i+1 && num[j]!= num[j-1]){  
         int rest = target - num[i] - num[j];  
         int low = j+1, high = num.length-1;  
         while(low < high){  
           int sum = num[low] + num[high];  
           if(sum == rest){  
             List<Integer> list = new ArrayList<Integer>();  
             list.add(num[i]);  
             list.add(num[j]);  
             list.add(num[low]);  
             list.add(num[high]);  
             rslt.add(list);  
             while(high > low && num[high] == num[--high]);  
             while(high > low && num[low] == num[++low]);  
           }  
           else if(sum > rest)  
             high--;  
           else  
             low++;  
         }  
         }  
       }  
       }  
     }  
     return rslt;    
   }  
 }  

This method can be generalized to k-sum.