# GeetCode Hub

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`

class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> res = new ArrayList<List<Integer>>(); int len = nums.length; if(len < 4){ return res; } Arrays.sort(nums); return kSum(nums, 0, 4, target); } private List<List<Integer>> kSum(int[] nums, int start, int k, int target){ List<List<Integer>> res = new ArrayList<List<Integer>>(); if(k==2){ return twoSum(nums, start, target); } else{ for(int i=start;i<nums.length-k+1;i++){ List<List<Integer>> kSumList = kSum(nums, i+1, k-1, target-nums[i]); if(kSumList != null && kSumList.size() > 0){ for(List<Integer> curr : kSumList){ curr.add(0, nums[i]); } res.addAll(kSumList); } while(i<nums.length-1 && nums[i] == nums[i+1]){ i++; } } return res; } } private List<List<Integer>> twoSum(int[] nums, int start, int target){ int i=start; int j= nums.length-1; List<List<Integer>> res = new ArrayList<List<Integer>>(); while(i<j){ int currSum = nums[i]+nums[j]; if(currSum < target){ i++; } else if(currSum > target){ j--; } else{ List<Integer> ans = new ArrayList<Integer>(); ans.add(nums[i]); ans.add(nums[j]); res.add(ans); while(i<j && nums[i] == nums[i+1]){ i++; } while(i<j && nums[j] == nums[j-1]){ j--; } i++; j--; } } return res; } }

The main concept of this question is to re-use the existing solved results of 2-sum problems and 3-sum problems, which we can directly append with the current result.

Time Complexity: O(n^3)

Space Complexity:O(n)  // for storing the results.

Easy
Medium
Medium