[LeetCode] 18. 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)

1. Call 3 sum.

public class Solution {
    
    public List> threeSum(int[] nums, int startI, int target) {
        int len = nums.length;
        List> ret = new ArrayList>();
        for(int i = startI; i < len; ++i){
            if(i > startI && nums[i-1] == nums[i])
                continue;
            int x = i+1;
            int y = len-1;
            while(x < y){
                int sum = nums[x] + nums[y] + nums[i];
                if(target == sum){
                    Integer[] res = {nums[x], nums[y], nums[i]};
                    ret.add(Arrays.asList(res));
                    --y;
                    while(y >= startI && nums[y+1] == nums[y]){
                        --y;
                    }
                    ++x;
                    while(x < len && nums[x-1] == nums[x]){
                        ++x;
                    }
                }else if(target < sum){
                    --y;
                    while(y >= startI && nums[y+1] == nums[y]){
                        --y;
                    }
                }else{
                    ++x;
                    while(x < len && nums[x-1] == nums[x]){
                        ++x;
                    }
                }
            }
        }
        
        return ret;
    }
    
    public List> fourSum(int[] nums, int target) {
        int len = nums.length;
        List> ret = new ArrayList>();
        Arrays.sort(nums);
        
        for( int i = 0; i < len -3; ++i){
            if(i > 0 && nums[i-1] == nums[i])
                continue;
            int j = i+1;
            int threeSumTarget = target - nums[i];
            List> resThree = threeSum(nums, j, threeSumTarget);
            
            for(List l : resThree){
                ArrayList t = new ArrayList(l);
                t.add(nums[i]);
                Collections.sort(t);
                ret.add(t);
            }
        }
        
        return ret;
    }
}

2. Build K Sum

public class Solution {
    
    public List> kSum(int[] nums, int startI, int target, int k) {
        
        int len = nums.length;
        
        List> ret = new ArrayList>();
        
        //        List> ret = null can not pass input [0] in 4 sum. All loop return immedicately, including twoSum. It can be controlled by if(4 > len) in main function.
        
        if(2 == k){
            
            // error : forgot to initialize the ret, List> ret = new ... was removed because line 44, ret = kSum(nums, i+1, target - nums[i], k-1);

            ret = new ArrayList>();
            
            int i = startI;
            int j = len -1;
            
            while(i < j){

                int sum = nums[i] + nums[j];
                if(sum == target){
                    List twoSumItem = new ArrayList();
                    twoSumItem.add(nums[i]);
                    twoSumItem.add(nums[j]);
                    ret.add(twoSumItem);
                    
                    // Here, forgot to increase and decrease index, time limit exceeded. Brain power depleted after 2 hour coding.
                    ++i;
                    while(i < len && nums[i-1] == nums[i]){
                        ++i;
                    }
                    --j;
                    while(j >= startI && nums[j+1] == nums[j]){
                        --j;
                    }
                // get the wrong sign, increasing decreasing index with wrong direction, get no answer or little answer.    
                }else if(sum < target){
                    ++i;
                    while(i < len && nums[i-1] == nums[i]){
                        ++i;
                    }
                }else{
                    --j;
                    while(j >= startI && nums[j+1] == nums[j]){
                        --j;
                    }
                }
            }
            
            return ret;
        }
        
        for(int i = startI; i < len; ++i){
            if(i > startI && nums[i-1] == nums[i])
                continue;
            
            // Tried to optmize code
            // Assigned ret as the return from k-1 sums, while forgot k-1 sums were called multiple times, previuos ret were washed out.
            /*
            ret = kSum(nums, i+1, target - nums[i], k-1);
            
            for(List l : ret){
                l.add(nums[i]);
            }
            */
            List> kMOneRes = kSum(nums, i+1, target - nums[i], k-1);
            for(List l : kMOneRes){
                l.add(nums[i]);
            }
            
            ret.addAll(kMOneRes);
            
        }

        return ret;
    }
    
    public List> fourSum(int[] nums, int target) {
        int len = nums.length;
        
        List> ret = new ArrayList>();
        if(4 > len)
            return ret;
        
        Arrays.sort(nums);
        
        ret = kSum(nums, 0, target, 4);
        
        for(List l : ret){
            Collections.sort(l);
        }

        return ret;
    }
}

3. Pariwise, them two sum. Good solution, reduce complexity to O(N^2), but it is not easy to handle replicated answer. Plus, it can be O(n^4) in worst case. Consider 0 0 0 0 0 1 1 1 1 1, target 1. HashMap : 0: (0, 0) ... , 1: (0, 1) ... , 2 : (1, 1) .... For each key, it contains a list with length O(n^2), Then for target 1 = key 0 + key 1, do pair-wise match between two O(n^2) lists. Could we remove duplicates before hand? It does not sounds possible. Another solution could be divide 4 sum into 0 + 4, 1 + 3, 2 + 2, 3 + 1, 4 + 0 then conquer?

3.

3.