388. Quartets to Target
A festival organiser has a list of stall fees in nums and wants to pick four different stalls whose fees together equal the fixed budget target.
Return every distinct quadruple of values [a, b, c, d] such that a + b + c + d = target, where the four fees come from four different positions of nums. Two quadruples are considered the same if they contain the same values with the same multiplicities, whatever their order, and each must be listed only once. The quadruples may be returned in any order, and the values inside a quadruple may be in any order. If there is none, return an empty array.
Example 1
- Input:
- nums = [2,-2,1,-1,0,0], target = 0
- Output:
- [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
- Explanation:
Sorted: -2,-1,0,0,1,2. The quadruples summing to 0 are [-2,-1,1,2], [-2,0,0,2] and [-1,0,0,1].
Example 2
- Input:
- nums = [5,5,5,5,5], target = 20
- Output:
- [[5,5,5,5]]
- Explanation:
Any four of the five 5s give 20, but all choices contain the same values, so [5,5,5,5] is listed once.
Example 3
- Input:
- nums = [1,2,3], target = 6
- Output:
- []
- Explanation:
There are fewer than four entries, so no quadruple exists.
Constraints
1 ≤ nums.length ≤ 300
-3 * 106 ≤ nums[i] ≤ 3 * 106
-3 * 106 ≤ target ≤ 3 * 106
How this problem is judged
- Answers
- Lists at every level may be in any order. Duplicates still count.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n^3)
- Space
- O(1) extra, apart from sorting and the output