620. Four Values That Add to a Target
Given n integers and a target, count the DISTINCT sets of four values that add to it. Two
sets are the same when they use the same four values, however they were arranged or wherever
they came from.
1 0 -1 0 -2 2, target 0 -> 3
2 2 2 2 2, target 8 -> 1
1 2 3 4, target 11 -> 0
## Not the same question as problem 298
Problem 298 takes FOUR SEPARATE LISTS and counts quadruples of INDICES, so repeated values
give repeated quadruples and the count can reach n^4. This takes ONE list and counts
distinct value sets, so 2 2 2 2 2 with target 8 answers 1, not 5.
Different input shape, different counting rule, different algorithm. Reading which is wanted is the first step, as it was in 606 and 614.
## One more loop around problem 606
Sort. Fix the outer two values with a double loop, and run the converging sweep on the rest:
for i, for j > i:
lo = j+1, hi = n-1
s = b[i] + b[j] + b[lo] + b[hi]
s < target -> lo += 1
s > target -> hi -= 1
s == target -> record, move both inward
Two fixed indices plus a linear sweep is O(n^3), down from O(n^4). The pattern generalises:
k-sum is O(n^(k-1)) this way, with the two-pointer sweep always handling the innermost
pair.
## Four duplicate skips now, not three
Each has the same justification as in 606, and there is one more because there is one more outer loop:
· i: skip when b[i] == b[i-1]
· j: skip when j > i+1 and b[j] == b[j-1]. The j > i+1 guard matters, otherwise the
first j of a new i is wrongly compared against b[i] itself
· after recording: advance lo past equal values, and pull hi back past equal values
That second one is the new trap. Without the j > i+1 guard, the input 0 0 0 0 loses its
only quadruple.
## Overflow
Four values near 10^9 sum to 4 * 10^9, past a signed 32 bit integer. Accumulate the sum in
64 bits even though each value fits.
## Boundaries
Fewer than four values answers 0. 0 0 0 0 answers 1.
## Cost
Time O(n^3). Space O(1) beyond the input.
Constraints - `0 ≤ n ≤ 400` - `-10^9 ≤ each value ≤ 10^9` - `-10^9 ≤ target ≤ 10^9`
Input
The first line contains two integers n and target.
The second line contains n integers. It is absent when n is 0.
Output
Print one integer, the number of distinct four-value sets that add to the target.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.