# 1498. Number of Subsequences That Satisfy the Given Sum Condition

• Time: $O(\texttt{sort})$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: int numSubseq(vector& nums, int target) { constexpr int kMod = 1'000'000'007; const int n = nums.size(); int ans = 0; vector pows(n, 1); // pows[i] = 2^i % kMod for (int i = 1; i < n; ++i) pows[i] = pows[i - 1] * 2 % kMod; sort(nums.begin(), nums.end()); for (int l = 0, r = n - 1; l <= r;) if (nums[l] + nums[r] <= target) { ans += pows[r - l]; ans %= kMod; ++l; } else { --r; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public int numSubseq(int[] nums, int target) { final int kMod = 1_000_000_007; final int n = nums.length; int ans = 0; int[] pows = new int[n]; // pows[i] = 2^i % kMod pows[0] = 1; for (int i = 1; i < n; ++i) pows[i] = pows[i - 1] * 2 % kMod; Arrays.sort(nums); for (int l = 0, r = n - 1; l <= r;) if (nums[l] + nums[r] <= target) { ans += pows[r - l]; ans %= kMod; ++l; } else { --r; } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def numSubseq(self, nums: List[int], target: int) -> int: kMod = 1_000_000_007 n = len(nums) ans = 0 nums.sort() l = 0 r = n - 1 while l <= r: if nums[l] + nums[r] <= target: ans += pow(2, r - l, kMod) l += 1 else: r -= 1 return ans % kMod