Problem statement

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

Solution

Let us sort numbers. Use two pointers, where the smallest one correspondes to the left poiner and the biggest one to the right pointer. Then for each beg find the biggest end where we have A[beg] + A[end] <= target. For all such subsequences we have 2**(end - beg) options.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def numSubseq(self, A, target):
        A, n = sorted(A), len(A)
        beg, end, ans, M, P = 0, len(A) - 1, 0, 10**9 + 7, [1]
        for i in range(n): P += [(P[-1] * 2) % M]
        while beg <= end:
            if A[beg] + A[end] > target:
                end -= 1
            else:
                ans += P[end - beg]
                beg += 1
        return ans % M