[Problem]

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)

[Analysis]

思路与3Sum一样。事实上NSum问题都可以递归到2Sum然后以O(n^(N-1))复杂度解决，有兴趣还可以进一步用分治法优化(两两解决2Sum问题并merge)。

 

[Solution]

import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Solution {    public List
     
      
       > fourSum(int[] num, int target) {        List
       
        
         > solution = new ArrayList
         
          
           >(); if (num.length < 4) { return solution; } Arrays.sort(num); for (int i = 0; i < num.length - 3; i++) { if (i > 0 && num[i] == num[i - 1]) { continue; // if current value is already tested as the first element, skip; } for (int j = i + 1; j < num.length - 2; j++) { if (j > i + 1 && num[j] == num[j - 1]) { continue; } // Do 2Sum int head = j + 1; int tail = num.length - 1; while (head < tail) { if (head > j + 1 && num[head] == num[head - 1]) { head++; continue; } if (tail < num.length - 1 && num[tail] == num[tail + 1]) { tail--; continue; } int sum = num[i] + num[j] + num[head] + num[tail]; if (sum == target) { solution.add(new ArrayList
           
            (Arrays.asList(num[i], num[j], num[head], num[tail]))); head++; tail--; } else if (sum > target) { tail--; } else { head++; } } } } return solution; }}