Given an array of integersnums
and an integertarget
. Return the number of non-empty subsequences ofnums
such that the sum of the minimum and maximum element on it is less or equal thantarget
. Since the answer may be too large, return it modulo 10^9 + 7. 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]
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)