Given an array of integers`nums`

and an integer`target`

. Return the number ofnon-emptysubsequences 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.Input:nums = [3,3,6,8], target = 10Output:6Explanation:There are 6 subsequences that satisfy the condition. (nums can have repeated numbers). [3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

This question first appeared in the Leetcode weekly contest 195, and again I was impressed by @lee215‘s solution. The first key point is that, as the question asks for the number of subsequences, **the order does not matter** – we can sort the array. With the sorted `nums`

, we can apply two pointers to find for qualified subarrays and for each subarray `nums[i:j]`

, there are 2^{j-i} possible combinations – `num[i+1...j-1]`

could be included or excluded.

#### Logic

With two pointers `left=0`

and `right=len(nums)-1`

, if `nums[left]+nums[right]>target`

, then move `right`

to the left; else, count the possible combinations and move `left`

to the right.

#### Code

```
class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
nums.sort()
ret = 0
l,r = 0,len(nums)-1
while l <= r:
if nums[l] + nums[r] > target:
r -= 1
else:
ret += pow(2,r-l,10**9 + 7)
l += 1
return ret % (10**9 + 7)
```