# 58.4Sum

## 1.Description(Medium)

Given an arra&#x79;_&#x53;\_of\_n\_integers, are there elements\_a_,_b_,_c_, an&#x64;_&#x64;\_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;
    }
```
