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: The solution set must not contain duplicate quadruplets.

  1. For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
  3. A solution set is:
  4. [
  5.   [-1,  0, 0, 1],
  6.   [-2, -1, 1, 2],
  7.   [-2,  0, 0, 2]
  8. ]

Solution:

  1. public class Solution {
  2.   public List<List<Integer>> fourSum(int[] num, int target) {
  3.     List<List<Integer>> res = new ArrayList<List<Integer>>();
  4.     Set<String> set = new HashSet<String>();
  6.     if (num == null || num.length < 4) {
  7.       return res;
  8.     }
  10.     Arrays.sort(num);
  12.     int n = num.length;
  14.     for (int i = 0; i < n - 3; i++) {
  15.       for (int j = i + 1; j < n - 2; j++) {
  16.         int m = j + 1;
  17.         int k = n - 1;
  19.         while (m < k) {
  20.           int sum = num[i] + num[j] + num[m] + num[k];
  22.           if (sum == target) {
  23.             String key = String.format("%d,%d,%d,%d", num[i], num[j], num[m], num[k]);
  25.             if (!set.contains(key)) {
  26.               set.add(key);
  28.               List<Integer> sol = new ArrayList<Integer>();
  29.               sol.add(num[i]);
  30.               sol.add(num[j]);
  31.               sol.add(num[m]);
  32.               sol.add(num[k]);
  33.               res.add(sol);
  34.             }
  36.             m++;
  37.             k--;
  38.           } else if (sum < target) {
  39.             m++;
  40.           } else {
  41.             k--;
  42.           }
  43.         }
  44.       }
  45.     }
  47.     return res;
  48.   }
  49. }

Time complexity: O(n^3)