[Leetcode]1498. 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.
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)