学步园

题目：

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、递归求解

2、暴力for循环求解。

递归方法中对所有情况进行了探测，对每一个当前元素，都有两种可能：包含和不包含。因此，包含的时候，将该元素加入到tmp结果集中，然后对剩下的数组进行探测，

探测返回之后再删除结果集中的该元素；若不包含，则直接对该元素之后的数组元素调用相同方法进行探测。

截止条件：当前tmp中已经有四个元素，即不再往下递归。结果有两种：1.这四个元素和为target，则加入到最终结果集rst中。2.和不等于target，则直接返回。

该方法缺点：超时。

代码如下：

public class _4Sum {
    private List<Integer> tmp = new LinkedList<Integer>();
    private List<List<Integer>> rst = new LinkedList<List<Integer>>();

     private void findFour(int[] num,int begin,int target){
         if(tmp.size()==4){
             if(target==0){
                 Integer[] t = tmp.toArray(new Integer[4]);
                 Arrays.sort(t);
                 List<Integer> tt = new LinkedList<Integer>();
                 Collections.addAll(tt, t);
                 if(!rst.contains(tt))
                     rst.add(tt);
             }
         }
         else{
             if(begin==num.length) return;
             else{
                 tmp.add(num[begin]);
                 findFour(num,begin+1,target-num[begin]);
                 tmp.remove(tmp.size()-1);

                 findFour(num,begin+1,target);
             }
         }
     }
     public List<List<Integer>> fourSum(int[] num, int target) {

         if(num.length<4){
             return rst;
         }
         findFour(num,0,target);
         return rst;
     }
    
    public static void main(String[] args) {
        _4Sum sum = new _4Sum();
        int[] num = {4,-9,-2,-2,-7,9,9,5,10,-10,4,5,2,-4,-2,4,-9,5};
        List<List<Integer>> list = sum.fourSum(num,-13);
        System.out.println(list);
    }
}

方法二：利用for循环的时候依然需要对条件进行判断。首先，四个数没有必要使用四个循环。之前有题目2Sum，使用O（n）即可搞定。因此，外面套两个循环，里面使用2Sum的方法即可。

两个循环注意减枝。即当前一个数字和当前数一样时，就直接跳过继续往下走。

2Sum的方法就不多说了。两个下标，一前一后。向中间靠拢查找和就行了。

该方法不超时。

AC代码：

public class _4Sum {
    private List<List<Integer>> rst = new LinkedList<List<Integer>>();
    public List<List<Integer>> fourSum(int[] num, int target) {
        if (num.length < 4) {
            return rst;
        }
        Arrays.sort(num);
        for (int i = 0; i <= num.length - 4; i++) {
            if (i > 0 && num[i] == num[i - 1])
                continue;
            for (int j = i + 1; j <= num.length - 3; j++) {
                if (j > i + 1 && num[j] == num[j - 1])
                    continue;
                int left = j + 1, right = num.length - 1;
                int t = target - num[i] - num[j];
                while (left < right) {
                    if(left>j+1 && num[left]==num[left-1] && left<right)
                        left++;
                    if(right<num.length-1 && num[right]==num[right+1] && left<right)
                        right--;
                    if(left<right){
                        if(t == (num[left] + num[right])){
                            List<Integer> tmp = new LinkedList<Integer>();
                            tmp.add(num[i]);
                            tmp.add(num[j]);
                            tmp.add(num[left]);
                            tmp.add(num[right]);
                            if(!rst.contains(tmp))
                                rst.add(tmp);
                            left++;
                            right--;
                        }
                        else if(t>(num[left] + num[right])){
                            left++;
                        }
                        else
                            right--;
                    }
                }
            }
        }

        return rst;
    }

    public static void main(String[] args) {
        _4Sum sum = new _4Sum();
        int[] num = {4,-9,-2,-2,-7,9,9,5,10,-10,4,5,2,-4,-2,4,-9,5};
        List<List<Integer>> list = sum.fourSum(num,-13);
        System.out.println(list);
    }
}