4Sum
Medium · Arrays & Hashing · Array · Two Pointers · Sorting
Problem
You are given an integer array nums and an integer target. Return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that a, b, c and d are four distinct indices and the four values add up to target.
Quadruplets are compared by their values: the result must not contain two quadruplets made of the same four values. The quadruplets, and the values inside each one, may be in any order.
Examples
Input: nums = [3,-1,0,2,-2,1], target = 2 Output: [[-2,-1,2,3],[-2,0,1,3],[-1,0,1,2]]
Three different groups of values add up to 2, for example -2 + -1 + 2 + 3.
Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]]
Many choices of four indices exist, but they all give the same values, so the quadruplet is listed once.
Input: nums = [1,2,3,4], target = 100 Output: []
The four values together add up to only 10.
Constraints
- 1 <= len(nums) <= 200
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
Approaches
- Baseline: every four indices — time O(n⁴), space O(q) for q distinct answers
Follow-up
The same structure handles k values for any k: fix one value, solve (k - 1)-sum on the rest, and finish with two pointers at k = 2. That costs O(n^(k-1)). If only the number of quadruplets is wanted and they come from four different lists, a hash map of pair sums brings it down to O(n²); see the first use case.
Related problems
Start free on Cariara · Coding problems · System design studio
