58.4Sum

1.Description(Medium)

Given an arrayS_of_n_integers, are there elements_a,b,c, andd_in_S_such that_a + b + c + d = target?

Find all unique quadruplets in the array which gives the sum of target.

Notice

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.

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)

2.Code

既然已经做了2sum, 3sum, 3sum closest。自然能推广到4sum。但这里希望能推广到更普遍的k-sum问题。这里使用递归的思路：

1. k-sum问题可以转化为(k-1)-sum问题：对于数组中每个数A[i]，在A[i+1:n-1]中寻找target-A[i]的(k-1)-sum问题。

2. 直到k=2时，用2sum的双指针扫描来完成。

去重复解的技巧和3Sum问题一模一样。

不过不过本题目中hashset的做法可以借鉴。

 public ArrayList<ArrayList<Integer>> fourSum(int[] numbers, int target) {
        ArrayList<ArrayList<Integer>> result=new ArrayList<>();
        if(numbers==null || numbers.length<4){
            return result;
        }
        Arrays.sort(numbers);
        HashSet<ArrayList<Integer>> set=new HashSet<>();
        for(int i=0;i<numbers.length-3;i++){
            for(int j=i+1;j<numbers.length-2;j++){

                int head=j+1;
                int tail=numbers.length-1;
                while(head<tail){
                    int sum=numbers[i]+numbers[j]+numbers[head]+numbers[tail];
                    if(sum>target){
                        tail--;
                    }
                    else if(sum<target){
                        head++;
                    }
                    else if(sum==target){
                        ArrayList<Integer> path=new ArrayList<Integer>();
                        path.add(numbers[i]);
                        path.add(numbers[j]);
                        path.add(numbers[head]);
                        path.add(numbers[tail]);

                        if(!set.contains(path)){
                            set.add(path);
                            result.add(path);
                        }

                        head++;
                        tail--;
                    }
                }
            }
        }
        return result;
    }