> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/two_sum/1498.-number-of-subsequences-that-satisfy-the-given-sum-condition.md).

# 1498. Number of Subsequences That Satisfy the Given Sum Condition

https\://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/

Given an array of integers `nums` and an integer `target`.

Return the number of **non-empty** subsequences of `nums` such that the sum of the minimum and maximum element on it is less or equal than `target`.

Since the answer may be too large, return it modulo 10^9 + 7.

**Example 1:**

```
Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)
```

**Example 2:**

```
Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
```

**Example 3:**

```
Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).
```

**Example 4:**

```
Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127
```

**Constraints:**

* `1 <= nums.length <= 10^5`
* `1 <= nums[i] <= 10^6`
* `1 <= target <= 10^6`

给定数组统计满足其中最大元素和最大元素的和小于等于target的子集合数目。不断且快速找最大最小 => 先sorting。sorting后观察到如果\[l, r]满足l + r <= target，那么l, r之间的任意组合都满足，无需遍历\[l, r - 1]，一共pow(2, r - l)个，l++；且如果\[l, r]不满足，\[l + 1, r]都不会满足，r-- => 双指针。重复计算2 \*\* (r - l) % M耗时过多，提前记录pow取值以复用。

```python
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort() 
        M, N = 1000000007, len(nums)
        l, r, res = 0, N - 1, 0
        pow = [1] * N
        for i in range(1, N):
            pow[i] = pow[i - 1] * 2 % M
        # pow = [2 ** i % M for i in range(len(nums))]
        while l <= r:
            if nums[l] + nums[r] <= target:
                # res = (res % M + 2 ** (r - l) % M) % M 
                # res += pow(2, r - l, M)
                res = (res + pow[r - l]) % M
                l += 1
            else:
                r -= 1
        return res
```