DiffPush Tier Arrays · Hard O(n^3) · O(1) auxiliary (excluding the output)
A calibration rig adjusts four independent dials recorded as signed integers and needs every distinct combination of four readings that lands exactly on a target offset. Each reading may be used at most once per combination, and combinations are reported by their values so reorderings count once.
Input: An array nums of n integers and an integer target.
Output: All distinct quadruples of values from nums that sum to target, with no duplicates and order not significant.
1 <= n <= 200-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9The quadruple requires four distinct indicesInput: {"nums":[1,0,-1,0,-2,2],"target":0}
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Three distinct value sets reach the target, with the repeated zero used at two different positions in one of them.
Input: {"nums":[2,2,2,2,2],"target":8}
Output: [[2,2,2,2]]
Only one distinct quadruple exists even though the value 2 can be chosen in many ways.