🐍 [ Python ] Simple Solution | 🚀 Optimal | 🔢 Two Pointer Sum Approach | ⏱️ O(n*log(n)) Approach
Runtime: 832 ms, faster than 68.92% of Python3 online submissions for Number of Subsequences That Satisfy the Given Sum Condition.\nMemory Usage: 29.5 MB, less 
*Runtime: 832 ms, faster than 68.92% of Python3 online submissions for Number of Subsequences That Satisfy the Given Sum Condition.\nMemory Usage: 29.5 MB, less than 8.18% of Python3 online submissions for Number of Subsequences That Satisfy the Given Sum Condition.*\n\nhere\'s a step-by-step explanation of the solution with some intuition behind each step:\nangelscript\n\n```\nclass Solution:\n    def numSubseq(self, nums: List[int], t: int) -> int:\n        if len(nums)==1:\n            return 1 if 2*nums[0]<=t else 0\n```\n\nThe function begins by checking if the input list nums contains only one element. If it does, the function returns 1 if the element is less than or equal to t/2, since the element itself is a valid subsequence that satisfies the condition. Otherwise, it returns 0, since there are no valid subsequences that satisfy the condition.\n\n\tnums.sort()\n\tl=0\n\tr=len(nums)-1\n\tc=0\n\tMOD = 10**9 + 7\n\n\nIf the input list nums contains more than one element, the function first sorts the list in non-decreasing order. This is necessary for the two-pointer approach to work correctly. The function initializes the left and right pointers l and r to the beginning and end of the sorted array, respectively. It also initializes a counter c to 0 and a constant MOD to 10^9 + 7.\n\n\twhile (l<=r):\n\t\tif nums[l]+nums[r]>t:\n\t\t\tr-=1\n\t\telse:\n\t\t\tc = (c + pow(2, r - l, MOD)) % MOD\n\t\t\tl += 1\n\n\nThe function then enters a loop that continues as long as the left pointer l is less than or equal to the right pointer r. Within the loop, the function checks if the sum of the elements pointed to by l and r is greater than t. If it is, the function decrements the right pointer r to move it closer to the left pointer l. This is because if the sum of the elements pointed to by l and r is greater than t, then moving the right pointer r to the left can only decrease the sum and make it more likely to satisfy the condition.\n\nIf the sum of the elements pointed to by l and r is less than or equal to t, the function updates the counter c to include all valid subsequences that start with the element pointed to by l. The number of such subsequences is 2^(r-l), since each element between nums[l+1] and nums[r] can either be included or excluded from the subsequence. The function uses modular arithmetic to compute 2^(r-l) % MOD, and adds the result to the counter c.\n\nAfter updating the counter c, the function increments the left pointer l to move it closer to the right pointer r. This is because if the sum of the elements pointed to by l and r is less than or equal to t, then moving the left pointer l to the right can only increase the sum and make it less likely to satisfy the condition.\n\n\treturn c\n\n\nFinally, after the loop has terminated, the function returns the counter c, which represents the total number of valid subsequences that satisfy the condition.\n\n```\nclass Solution:\n    def numSubseq(self, nums: List[int], t: int) -> int:\n        if len(nums)==1:\n            return 1 if 2*nums[0]<=t else 0\n        nums.sort()\n        l=0\n        r=len(nums)-1\n        c=0\n        MOD = 10**9 + 7\n        while (l<=r):\n            if nums[l]+nums[r]>t:\n                r-=1\n            else:\n                c = (c + pow(2, r - l, MOD)) % MOD\n                l += 1\n        return c\n```\n\nA simple upvote would make my day ... Thank You
['Array', 'Two Pointers', 'Sorting', 'Python']