1. Description

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.

2. Runtime Distribution

3. Submission Details

4. 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]
]

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

class Tuple {
	public X x;
	public Y y;

	public Tuple() {
	}

	public Tuple(X x, Y y) {
		this.x = x;
		this.y = y;
	}
}

public List> fourSum(int[] num, int target) {

	final List> result = new ArrayList<>();
	final int length;

	if (num == null || (length = num.length) < 4) {
		return result;
	}

	Arrays.sort(num);

	if ((num[0] << 2) > target || (num[length - 1] << 2) < target) {
		return result;
	}

	Set> reseltSet = new HashSet<>();
	DivideSum2(num, target, reseltSet);

	return new ArrayList>(reseltSet);
}

private void DivideSum2(int[] num, int target, Set> reseltSet) {

	Map>> map = new HashMap<>();

	for (int i = 0; i < num.length; i++) {

		if (i > 1 && num[i] == num[i - 2]) {
			continue;
		}
		for (int j = i + 1; j < num.length; j++) {

			if (j > i + 2 && num[j] == num[j - 2]) {
				continue;
			}

			int sum21 = num[i] + num[j];
			int sum22 = target - sum21;

			if (map.containsKey(sum22)) {
				check(num, map.get(sum22), i, j, reseltSet);
			}

			List> list = map.get(sum21);
			if (list == null) {
				list = new ArrayList<>();
				map.put(num[i] + num[j], list);
			}
			list.add(new Tuple(i, j));
		}
	}
}

private void check(int[] nums, List> list, int index1, int index2,
		Set> results) {

	for (Tuple tuple : list) {

		if (tuple.x == index1 || tuple.x == index2 || tuple.y == index1 || tuple.y == index2) {
			continue;
		} else {
			List result = Arrays.asList(nums[tuple.x], nums[tuple.y], nums[index1], nums[index2]);
			Collections.sort(result);
			results.add(result);
		}
	}
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class LeetCode0018 {

	class Tuple {
		public X x;
		public Y y;

		public Tuple() {
		}

		public Tuple(X x, Y y) {
			this.x = x;
			this.y = y;
		}
	}

	public List> fourSum(int[] num, int target) {

		final List> result = new ArrayList<>();
		final int length;

		if (num == null || (length = num.length) < 4) {
			return result;
		}

		Arrays.sort(num);

		if ((num[0] << 2) > target || (num[length - 1] << 2) < target) {
			return result;
		}

		Set> reseltSet = new HashSet<>();
		DivideSum2(num, target, reseltSet);

		return new ArrayList>(reseltSet);
	}

	private void DivideSum2(int[] num, int target, Set> reseltSet) {

		Map>> map = new HashMap<>();

		for (int i = 0; i < num.length; i++) {

			if (i > 1 && num[i] == num[i - 2]) {
				continue;
			}
			for (int j = i + 1; j < num.length; j++) {

				if (j > i + 2 && num[j] == num[j - 2]) {
					continue;
				}

				int sum21 = num[i] + num[j];
				int sum22 = target - sum21;

				if (map.containsKey(sum22)) {
					check(num, map.get(sum22), i, j, reseltSet);
				}

				List> list = map.get(sum21);
				if (list == null) {
					list = new ArrayList<>();
					map.put(num[i] + num[j], list);
				}
				list.add(new Tuple(i, j));
			}
		}
	}

	private void check(int[] nums, List> list, int index1, int index2,
			Set> results) {

		for (Tuple tuple : list) {

			if (tuple.x == index1 || tuple.x == index2 || tuple.y == index1 || tuple.y == index2) {
				continue;
			} else {
				List result = Arrays.asList(nums[tuple.x], nums[tuple.y], nums[index1], nums[index2]);
				Collections.sort(result);
				results.add(result);
			}
		}
	}

	public static void main(String[] args) {
		LeetCode0018 leetcode = new LeetCode0018();
		int[] nums = new int[] { 1, 0, -1, 0, -2, 2 };

		List> results = leetcode.fourSum(nums, 0);

		for (List list : results) {
			for (Integer number : list) {
				System.out.print(number + " ");
			}
			System.out.println();
		}
	}
}

[/restab]
[/restabs]