[Leetcode] 1498. Number of Subsequences That Satisfy the Given Sum Condition

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

initial

so i got till sliding window part but how to calc number of subsequences??

from left to right pointer we have right-left positions cuz we have left+1, left+2, ... until right and r-(l+1)+1= r-l

Then for each position we have 2 options- whether to take this value in that position or not so its 2(r-l) number of possibilities that include the leftmost value**, so thats the formula to use

sol

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        ans=0
        length=len(nums)
        nums.sort()
        left,right=0,length-1
        MOD= 10**9+7
        while left<=right:
            if (nums[left]+nums[right])%MOD>target:
                right-=1
            else:
                ans+=2**(right-left)
                left+=1
        return ans%MOD

complexity

n time
1 space