Problem statement

https://binarysearch.com/problems/Min-Max-Sets/

Solution

Equal to Leetcode 1498. Number of Subsequences That Satisfy the Given Sum Condition.

Complexity

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

Code

class Solution:
    def solve(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]
        while beg <= end:
            if A[beg] + A[end] > target:
                end -= 1
            else:
                ans += P[end - beg]
                beg += 1
        return ans