LeetCode - Medium - 18. 4Sum

Topic

• Array
• Hash Table
• Two Pointers

Description

https://leetcode.com/problems/4sum/

Given an array

nums

of n integers and an integer

target

, are there elements a, b, c, and d in

nums

such that a + b + c + d =

target

? Find all unique quadruplets in the array which gives the sum of target.

Notice that the solution set must not contain duplicate quadruplets.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
           

Example 2:

Input: nums = [], target = 0
Output: []
           

Constraints:

• 0 <= nums.length <= 200
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹

Analysis

General Idea

If you have already read and implement the 3sum and 4sum by using the sorting approach: reduce them into 2sum at the end, you might already got the feeling that, all ksum problem can be divided into two problems:

1. 2sum Problem
2. Reduce K sum problem to K – 1 sum Problem

Therefore, the ideas is simple and straightforward. We could use recursive to solve this problem. Time complexity is O(N^(K-1)).

Submission

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {
	public List<List<Integer>> fourSum(int[] nums, int target) {
		Arrays.sort(nums);
		return kSum(nums, 0, 4, target);
	}

	private List<List<Integer>> kSum(int[] nums, int start, int k, int target) {
		int len = nums.length;
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		if (k == 2) { // two pointers from left and right
			int left = start, right = len - 1;
			while (left < right) {
				int sum = nums[left] + nums[right];
				if (sum == target) {
					List<Integer> path = new ArrayList<Integer>();
					path.add(nums[left]);
					path.add(nums[right]);
					res.add(path);
					while (left < right && nums[left] == nums[left + 1])
						left++;
					while (left < right && nums[right] == nums[right - 1])
						right--;
					left++;
					right--;
				} else if (sum < target) { // move left
					left++;
				} else { // move right
					right--;
				}
			}
		} else {
			for (int i = start; i < len - (k - 1); i++) {
				if (i > start && nums[i] == nums[i - 1])
					continue;
				List<List<Integer>> temp = kSum(nums, i + 1, k - 1, target - nums[i]);
				for (List<Integer> t : temp) {
					t.add(0, nums[i]);
				}
				res.addAll(temp);
			}
		}
		return res;
	}
}
           

Test

import static org.junit.Assert.*;

import java.util.Arrays;

import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder;

import org.hamcrest.collection.IsEmptyCollection;
import org.junit.Test;

public class FourSumTest {

	@Test
	@SuppressWarnings("unchecked")
	public void test() {
		FourSum obj = new FourSum();

		assertThat(obj.fourSum(new int[] {}, 0), IsEmptyCollection.empty());
		assertThat(obj.fourSum(new int[] { 1, 0, -1, 0, -2, 2 }, 0), containsInAnyOrder(Arrays.asList(-2, -1, 1, 2),
				Arrays.asList(-2, 0, 0, 2), Arrays.asList(-1, 0, 0, 1)));
	}
}