Count how many non-empty subsequences have the sum of the smallest and largest chosen values within a target limit.
Problem
Given an integer array nums and an integer target, count the number of non-empty subsequences such that the sum of the minimum and maximum element in the subsequence is less than or equal to target.
A subsequence is formed by deleting zero or more elements from the array without changing the order of the remaining elements.
Return the number of valid subsequences modulo .
Key idea of the task
You do not need to list the subsequences. Only determine how many of them satisfy the condition based on their smallest and largest values.
Input Format
nums: an integer arraytarget: an integer limit
The array may contain duplicate values.
Output Format
Return a single integer: the number of non-empty subsequences whose minimum plus maximum is at most target, modulo .
Constraints
- Count only non-empty subsequences.
- A subsequence is determined by indices, so equal values at different positions are treated as different choices.
- The answer should be returned modulo .
- Use an approach that is efficient for large arrays; brute force enumeration is not feasible.
Example 1
Input
nums = [3,5,6,7], target = 9
Output
4
Explanation
Valid subsequences are [3], [3,5], [3,6], and [3,5,6]. For each of these, the minimum plus maximum is at most 9.
Example 2
Input
nums = [3,3,6,8], target = 10
Output
6
Explanation
After sorting, valid choices can be counted by pairing the smallest usable element with the largest usable element and counting all subsets in between.
Show 1 more example
Example 3
Input
nums = [2,3,3,4,6,7], target = 12
Output
61
Explanation
There are many valid subsequences; counting them efficiently requires sorting plus a two-pointer or equivalent counting strategy.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.