Quadruplets That Hit the Target
MediumTwo Pointers
Problem
A portfolio tool wants every way to pick four assets from nums (four different positions) whose values add up exactly to target.
Return all distinct value quadruplets. The order of the quadruplets and of the values inside each one does not matter.
Example 1
- Input:
- nums = [2, -1, 0, 1, -2, 0], target = 0
- Output:
- [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
These are the only distinct value sets of size four that sum to 0.
Example 2
- Input:
- nums = [3, 3, 3, 3, 3], target = 12
- Output:
- [[3, 3, 3, 3]]
Example 3
- Input:
- nums = [1, 2, 3], target = 6
- Output:
- []
Fewer than four values.
Constraints
- 0 ≤ nums.length ≤ 200
- -10^9 ≤ nums[i] ≤ 10^9
- -10^10 ≤ target ≤ 10^10
Hint
Show the first hint
You already know how to find all pairs in a sorted range with a given sum. How many values must you fix to reduce this to that?
Walkthrough
How to approach it
01Clarify before coding
- Distinct by values, not positions? Yes.
- Can sums exceed 32 bits? Yes: four values of 10^9 sum to 4·10^9. Use 64-bit arithmetic in typed languages.
- Order of output? Any.
02Brute force
Try all 4-index combinations, sort each match and deduplicate with a set.
Cost: O(n⁴): about 6.5·10^7 combinations for n = 200, plus set overhead; too slow in an interpreted language and not scalable.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.