LC 1498 [M] Number of Subsequences That Satisfy the Given Sum Condition - ALawliet/algorithms GitHub Wiki

similar to two-sum

class Solution:
    def numSubseq(self, A, target):
        A.sort()
        res = 0
        toobigmod = 10**9 + 7
        
        l = 0
        r = len(A) - 1
        
        while l <= r:
            S = A[l] + A[r] 
            if S > target: # it's too big so shrink the right to get a smaller sum
                r -= 1
            else: # it has room so move up to extend the subsequence
                res += pow(2, r - l, toobigmod) # wow it has 3 args to mod at the end
                l += 1
                
        return res % toobigmod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort() # the examples kind of imply this, but we need to make sure it's done
        res = 0
        toobigmod = (10**9 + 7) # just for LC TLE
        
        r = len(nums) - 1
        for l in range(len(nums)):
            while (nums[l] + nums[r]) > target and l <= r:
                r -= 1 # shrink the right side until it fits
            if l <= r:
                res += pow(2, r-l) # if we start with 3,3,6 and i=0 so 3 is chosen and implied, then there are only 2^[i=1,i=2] = 2^2 subsequences, and since it is sorted if 3,3,6 <= 9, then we can't include any after 6
                res %= toobigmod # just for LC TLE
        return res