hardTwo PointersPure DSA~30 min
Count Subsequences Where Min Plus Max Fits a Budget
From a pool of item weights, count non-empty subsets whose lightest plus heaviest item is within a budget. Because subsets are unordered, only the min and max matter.
Problem
Given an integer array nums and an integer target, return the number of non-empty subsequences such that the sum of the minimum and maximum element in the subsequence is <= target. Since the answer may be large, return it modulo 1e9 + 7.
Input
An integer array nums and an integer target.
Output
An integer: the count of qualifying subsequences modulo 1e9 + 7.
Constraints
- 1 <= nums.length <= 100000
- 1 <= nums[i] <= 10^6; 1 <= target <= 10^6
Examples
Example 1
Input
nums = [3,5,6,7], target = 9
Output
4
[3],[3,5],[3,5,6],[3,6] each have min+max <= 9.
Example 2
Input
nums = [3,3,6,8], target = 10
Output
6
Six subsequences satisfy the bound.