Count Subsequences with a Bounded Minimum-Plus-Maximum
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Count nonempty subsequence occurrences whose minimum value plus maximum value is at most target. A single selected value contributes twice itself to this test. Subsequences are distinguished by chosen original positions,including equal-valued positions. Return the count modulo 1000000007.
```cpp
class Solution {
public:
int numSubseq(vector<int>& nums, int target);
};
```
### Examples
**Example 1:**
```text
Input: nums = [1,2,4], target = 5
Output: 5
Explanation: The valid choices are[1],[2],[1,2],[1,4],and[1,2,4].
```
**Example 2:**
```text
Input: nums = [2,2], target = 4
Output: 3
Explanation: Each of the two singleton occurrences and the pair qualify.
```
### Constraints
- nums has length 1 to 100000.
- Every value and target lie in `[1,1000000]`.
### Contract considerations
The result is a count modulo the stated modulus; no output-order freedom applies.
```hint Read the boundary condition
Count nonempty choices of original positions, including equal-valued positions. Check singletons and equality at the minimum-plus-maximum bound.
```
### Boundary reminders
The result is a count modulo the stated modulus; no output-order freedom applies.
Overview: Count Subsequences with a Bounded Minimum-Plus-Maximum. Count nonempty subsequence occurrences whose minimum value plus maximum value is at most target.
