# 0018. 4Sum

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

## Description

Given an array `nums` of `n` integers, return *an array of all the **unique** quadruplets* `[nums[a], nums[b], nums[c], nums[d]]` such that:

* `0 <= a, b, c, d < n`
* `a`, `b`, `c`, and `d` are **distinct**.
* `nums[a] + nums[b] + nums[c] + nums[d] == target`

You may return the answer in **any order**.

**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 = [2,2,2,2,2], target = 8
**Output:** [[2,2,2,2]]
```

**Constraints:**

* `1 <= nums.length <= 200`
* `-109 <= nums[i] <= 109`
* `-109 <= target <= 109`

## ac

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

    private List<List<Integer>> helper(int[] nums, int start, int ksum, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        // exit
        if (start >= nums.length) return res;

        if (ksum == 2) {
            int l = start, r = nums.length - 1;
            while (l < r) {
                int sum = nums[l] + nums[r];
                if (sum == target) {
                    List<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(nums[l]);
                    tmp.add(nums[r]);
                    res.add(tmp);
                    // skip duplicate
                    while (l < r && nums[l] == nums[l+1]) l++;
                    while (l < r && nums[r] == nums[r-1]) r--;
                    l++;
                    r--;
                } else if (sum < target) {
                    l++;
                } else {
                    r--;
                }
            }
            return res;
        }

        // recursion
        for (int i = start; i <= nums.length - ksum; i++) {
            if (i > start && nums[i] == nums[i-1]) continue; // skip duplicate
            // child result
            List<List<Integer>> child = helper(nums, i+1, ksum-1, target-nums[i]);
            for (List<Integer> list : child) {
                list.add(nums[i]);
            }
            res.addAll(child);
        }

        return res;
    }
}

/*
sort, recursion till 2sum
*/
```