Easy Understand | Simple Method | Binary Exponentiation | Java | Python | C++✅
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst, the array needs to be sorted so that the array is monotonic so that it easy to b
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst, the array needs to be sorted so that the array is monotonic so that it easy to be operational by binary search\n![image.png](https://assets.leetcode.com/users/images/e648f8cc-1b06-475d-899a-c2a91700acc4_1683337415.3123298.png)\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAfter sorting the array, the array has monotonicity.\n\nWe randomly find a continuous sub-array, the left boundary of this sub-array must be the smallest number in the sub-array (because it has been sorted before), denoted as `L`, and the right boundary of the sub-array must be the largest sub-array denoted as `R`.\n\nIf `L+R<=target`, then we only need to keep the left boundary `L `unchanged, and the right boundary `R` can be any number smaller than `R`.\n\nStep:\n- sort the array `nums`\n- Traverse each number of the array as the left boundary `L`.\n- According to the left boundary `L`, use the binary search to find the qualified right boundary `R`\n- After determining L and R, any permutation and combination of numbers between (L+1)-R meets the requirements (the number is 2 to the power of R-L)\n- Just add all the results together, the specific code is as follows\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nlogn)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n``` Java []\nclass Solution {\n    final static int MOD = (int)1e9+7;\n    public int numSubseq(int[] nums, int target) {\n        Arrays.sort(nums);\n        int n = nums.length;\n        int[] f = new int[n];\n        f[0] = 1;\n        for (int i = 1; i < n; i++)\n            f[i] = (f[i - 1] << 1) % MOD;\n        int l = 0, r = n-1;\n        int ans = 0;\n        while (l <= r) {\n            if (nums[l] + nums[r] > target)\n                r--;\n            else {\n                ans = (ans + f[r - l]) % MOD;\n                l++;\n            }\n        }\n        return ans;\n    }\n}\n```\n``` Python3 []\nclass Solution:\n    def numSubseq(self, nums: List[int], target: int) -> int:\n        # Optimized, beats 97%\n        MOD = 10**9 + 7\n        f = [1] + [0] * (len(nums)-1)\n        for i in range(1, len(nums)):\n            f[i] = f[i - 1] * 2 % MOD\n        nums.sort()\n        ans = 0\n        for i, num in enumerate(nums):\n            if nums[i] * 2 > target:\n                break\n            maxValue = target - nums[i]\n            pos = bisect.bisect_right(nums, maxValue) - 1\n            ans += f[pos - i] if pos >= i else 0\n        return ans % MOD\n```\n``` C++ []\nclass Solution {\npublic:\n    int numSubseq(vector<int>& nums, int target) {\n        int mod = 1e9 + 7;\n        int res = 0, n = nums.size(), l = 0, r = n - 1;\n        vector<int> pows(n, 1);\n        for (int i = 1 ; i < n ; ++i)\n            pows[i] = pows[i - 1] * 2 % mod;\n        sort(nums.begin(), nums.end());\n        while (l <= r) {\n            if (nums[l] + nums[r] > target) {\n                r--;\n            } else {\n                res = (res + pows[r - l]) % mod;\n                l++;\n            }\n        }\n        return res;\n    }\n};\n```
['Two Pointers', 'Binary Search', 'C++', 'Java', 'Python3']