# 018-4sum

## Question

https://leetcode.com/problems/4sum/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.

Example:

``````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]
]
``````

## Thought Process

1. Brute Force
2. Time complexity O(n^4)
3. Space complexity O(1)
2. Recursive solution
1. Use backtrack to facilitate the process
2. Finding 4 sum is equivalent of finding 3 sum with current element
3. Finding 3 sum is equivalent of finding 2 sum with the first element of remaining element
4. Time complexity O(n^3)
5. Extra space complexity O(k)

## Solution

``````class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 4) return res;
Arrays.sort(nums);
kSum(nums, target, 4, 0, res, new ArrayList<>());
return res;
}

private void kSum(int[] nums, int target, int k, int start, List<List<Integer>> res, List<Integer> path) {
if (k == 2) {
int lo = start, hi = nums.length - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
if (sum < target) {
lo++;
} else if (sum > target) {
hi--;
} else {
List<Integer> sol = new ArrayList<>(path);
lo++;
hi--;
while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
}
}
} else {
for (int i = start; i <= nums.length - k; i++) {
// skip the duplicate element
if (i > start && nums[i] == nums[i - 1]) continue;
// skip the element that is too small even summing with the k - 1
// largest element
if (nums[i] + (k - 1) * nums[nums.length - 1] < target) continue;
// the remaining element is too big to reach target, skip remaining elements
if (nums[i] * k > target) break;
// corner case where the target is multiple of current element
if (nums[i] * k == target) {
if (nums[i + k - 1] == nums[i]) {
List<Integer> sol = new ArrayList<>(path);
for (int j = 0; j < k; j++) sol.add(nums[i]);
}
break;
}