Python🔥Java🔥C++🔥Simple Solution🔥Easy to Understand
!! BIG ANNOUNCEMENT !!\nI am currently Giving away my premium content well-structured assignments and study materials to clear interviews at top companies relat
**!! BIG ANNOUNCEMENT !!**\nI am currently Giving away my premium content well-structured assignments and study materials to clear interviews at top companies related to computer science and data science to my current Subscribers. I planned to give for next 10,000 Subscribers as well. If you\'re interested **DON\'T FORGET** to Subscribe\n\n# Search \uD83D\uDC49 `Tech Wired Leetcode` to Subscribe\n\n# Video Solution \n\n# Search \uD83D\uDC49 `Number of Subsequences That Satisfy the Given Sum Condition by Tech Wired `\n\n# or\n\n# Click the Link in my Profile\n\n# Approach:\n\n- Sort the given array in non-decreasing order.\n- Initialize two pointers left and right to the first and last indices of the array respectively.\n- Initialize a variable count to 0.\n- Iterate the loop until left is less than or equal to right.\n- If the sum of elements at indices left and right is greater than the given target, decrement the right pointer.\n- Otherwise, the subsequence formed by elements at indices left and right and all the possible subsequences formed by the elements between them (i.e., from left+1 to right-1) will satisfy the given sum condition.\n- The number of possible subsequences that can be formed by the elements between left and right is equal to 2^(right-left).\n- Increment count by the number of possible subsequences and move left to the right.\n- After the loop, return the value of count-1 modulo 10^9 + 7.\n\n# Intuition:\n\nThe approach uses the fact that a subsequence can be formed by selecting any number of elements from a given array, without changing their relative order. Since the array is sorted in non-decreasing order, we can use a two-pointer approach to identify the elements that can be included in a subsequence that satisfies the given sum condition. We start by considering the first and last elements of the array. If their sum is greater than the given target, we decrement the last pointer. Otherwise, we include the last element in all possible subsequences that can be formed with the first element, and move the first pointer to the right. We repeat this process until the first pointer reaches the last pointer. Finally, we subtract 1 from the count to exclude the empty subsequence, and return the result modulo 10^9 + 7.\n\n```Python []\nclass Solution:\n    def numSubseq(self, nums: List[int], target: int) -> int:\n        nums.sort()\n        left, right = 0, len(nums) - 1\n        count = 0\n        mod = 10 ** 9 + 7\n        \n        while left <= right:\n            if nums[left] + nums[right] > target:\n                right -= 1\n            else:\n                count += pow(2, right - left, mod)\n                left += 1\n        \n        return count % mod\n\n\n```\n```Java []\nclass Solution {\n    public int numSubseq(int[] nums, int target) {\n        Arrays.sort(nums);\n        int res = 0, n = nums.length, left = 0, right = n - 1, mod = (int)1e9 + 7;\n        int[] pows = new int[n];\n        pows[0] = 1;\n        for (int i = 1 ; i < n ; ++i)\n            pows[i] = pows[i - 1] * 2 % mod;\n        while (left <= right) {\n            if (nums[left] + nums[right] > target) {\n                right--;\n            } else {\n                res = (res + pows[right - left++]) % mod;\n            }\n        }\n        return res;\n    }\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    int numSubseq(vector<int>& nums, int target) {\n        sort(nums.begin(), nums.end());\n        int res = 0, n = nums.size(), left = 0, right = n - 1, mod = 1e9 + 7;\n        vector<int> pows(n);\n        pows[0] = 1;\n        for (int i = 1 ; i < n ; ++i)\n            pows[i] = pows[i - 1] * 2 % mod;\n        while (left <= right) {\n            if (nums[left] + nums[right] > target) {\n                right--;\n            } else {\n                res = (res + pows[right - left++]) % mod;\n            }\n        }\n        return res;\n    }\n};\n\n```\n# An Upvote will be encouraging \uD83D\uDC4D
['Binary Search', 'Sorting', 'C++', 'Java', 'Python3']