Java | 2 pointers | Explained
Idea:\n sum(min, max) must be \u2264 target, so it doesn\'t matter what the numbers in between are\n Number of subsequences of length n that must start with a g
**Idea:**\n* sum(min, max) must be \u2264 target, so it doesn\'t matter what the numbers in between are\n* Number of subsequences of length `n` that must start with a give number = 2 ^ (n - 1). This is because for each number except the first one, there is a choice to include it or exclude it, so 1 x 2 x 2 ... (n - 1) times = 2 ^ (n - 1)\n* If numbers are in sorted order, the first number will be the min and last num will be max in the subsequence\n* Since we\'re counting subsequences, sorting `nums` will not effect the result, so do it\n* Use 2 pointers (L and R) pointing at max and min of the subsequence\n* If `A[L] + A[R] \u2264 T`, then all the possible subsequences are valid, so count them in and increment L\n* Else decrement R\n* Java\'s primitive data types can\'t contain large powers of a number, unless you want to use `BigInteger`, so use an array to store 2\'s powers % MOD\n\n**Example:**\n![image](https://assets.leetcode.com/users/images/06d1603c-2e07-4bd8-b8cf-9bc979416e11_1683338186.76141.png)\n>**T/S:** O(n lg n)/O(n), where n = size(nums)\n```\nprivate static final int MOD = (int) (1e9 + 7);\n\npublic int numSubseq(int[] nums, int target) {\n\tvar count = 0L;\n\tvar n = nums.length;\n\tvar powTwo = getTwoPowers(n);\n\tArrays.sort(nums);\n\n\tfor (int left = 0, right = n - 1; left <= right; ) {\n\t\tif (nums[left] + nums[right] <= target)\n\t\t\tcount += powTwo[right - left++];\n\t\telse\n\t\t\tright--;\n\t}\n\n\treturn (int) (count % MOD);\n}\n\nprivate int[] getTwoPowers(int n) {\n\tvar powTwo = new int[n];\n\tpowTwo[0] = 1;\n\n\tfor (var i = 1; i < n; i++)\n\t\tpowTwo[i] = (powTwo[i - 1] << 1) % MOD;\n\t\t\n\treturn powTwo;\n}\n```\n***Please upvote if this helps***
['Java']