[Python 3] From Brute force to Two Pointers Solution - Clean & Concise
\u274C Solution 1: Brute force (TLE)\n- We try all non-empty subsequences of the nums array, finding the min and max elements within each subsequence. We then c
**\u274C Solution 1: Brute force (TLE)**\n- We try all non-empty subsequences of the `nums` array, finding the `min` and `max` elements within each subsequence. We then check if `min + max <= target`; if so, the subsequence is valid.\n- If nums has N elements, then there will be `2^N` subsequences.\n\n```python\nclass Solution:\n    def numSubseq(self, nums: List[int], target: int) -> int:\n        n = len(nums)\n        MOD = int(1e9) + 7\n        ans = 0\n        for mask in range(1, 1 << n):\n            minElement = math.inf\n            maxElement = -math.inf\n            for i in range(n):\n                if (mask >> i) & 1:\n                    minElement = min(minElement, nums[i])\n                    maxElement = max(maxElement, nums[i])\n            \n            if minElement + maxElement <= target:\n                ans = (ans + 1) % MOD\n\n        return ans\n```\nComplexity:\n- Time: `O(N * 2^N)`, where `N <= 10^5` is length of `nums` array.\n- Space: `O(1)`\n\n---\n**\u2714\uFE0F Solution 2: Two Pointers**\n- In this problem, we count number of valid subsequences, which also means counting number of valid subsets in `nums` array.\n- We count all the subsets where the `min` is the smallest element and `max` is the largest element in the subset, such that `min + max <= target`.\n- The idea is to sort the `nums` array in non-descending order (no need to worry about the original order anymore)\n- We implement two pointers, where `left` is the index pointing to the first element, and `right` is the index pointing to the last element.\n- If `nums[left] + nums[right] <= target`, then we have subsets that take elements within the range `nums[left..right]` to form valid subsets that satisfy the problem requirements.\n   - To count the number of valid subsets efficiently, we assume the subsets always contains the `nums[left]` element, combined with all possible subsets (including empty ones) of the elements in the range `nums[left+1...right]`. \n   - Thus, there will be `2^(right - left)` total subsets. It\'s because there are `2^(right-left)` subsets of elements in `nums[left+1..right]`.\n   - After counting `nums[left]`, we increment `left` by 1.\n- Otherwise, if `nums[left] + nums[right] > target`, then we decrement `right` by 1 to reduce the sum.\n\n```python\nclass Solution:\n    def numSubseq(self, nums: List[int], target: int) -> int:\n        nums.sort()\n        MOD = int(1e9) + 7\n        n = len(nums)\n        POW2 = [1] * (n+1)\n        for i in range(n):\n            POW2[i+1] = POW2[i] * 2 % MOD\n\n        left = 0\n        right = len(nums) - 1\n        ans = 0\n        while left <= right:\n            if nums[left] + nums[right] <= target:\n                ans = (ans + POW2[right - left]) % MOD\n                left += 1\n            else:\n                right -= 1\n        return ans\n```\nComplexity:\n- Time: `O(NlogN)`, where `N <= 10^5` is length of `nums` array.\n- Space: `O(N)`\n\n\n\nCertainly! Here\'s the translation of the Vietnamese explanation into English:\n\n---\n**Let analyze an example for better understanding:** \nExample: nums = [1, 1, 3, 5, 7], target = 6\n\n**Step 1: left = 0, right = 4**\nnums[0] + nums[4] = 1 + 7 > 6\n\n- There are no valid subsequences that take `nums[0]` as the minimum and `nums[4]` as the maximum. So, decrement `right` by 1 (`right -= 1`).\n\n**Step 2: left = 0, right = 3**\nnums[0] + nums[3] = 1 + 5 <= 6\n- Always pick `nums[0]`\n- Consider all subsequences from elements in `nums[1...3]`:\n  - []\n  - [nums[1]]\n  - [nums[2]]\n  - [nums[3]]\n  - [nums[1], nums[2]]\n  - [nums[1], nums[3]]\n  - [nums[2], nums[3]]\n  - [nums[1], nums[2], nums[3]]\n- When combined with `nums[0]`, the valid subsequences are:\n  - [nums[0]]\n  - \\[nums\\[0\\], nums\\[1\\]\\]\n  - \\[nums\\[0\\], nums\\[2\\]\\]\n  - \\[nums\\[0\\], nums\\[3\\]\\]\n  - \\[nums\\[0\\], nums\\[1\\], nums\\[2\\]\\]\n  - \\[nums\\[0\\], nums\\[1\\], nums\\[3\\]\\]\n  - \\[nums\\[0\\], nums\\[2\\], nums\\[3\\]\\]\n  - \\[nums\\[0\\], nums\\[1\\], nums\\[2\\], nums\\[3\\]\\]\n- We have considered all the valid subsequences containing `nums[0]`, so increment `left` by 1 (`left += 1`).\n    \n**Step 3: left = 1, right = 3**\nnums\\[1\\] + nums\\[3\\] = 1 + 5 <= 6\n\n- Always pick `nums[1]`\n- Consider all subsequences from elements in `nums[2..3]`:\n  - \\[\\]\n  - \\[nums\\[2\\]\\]\n  - \\[nums\\[3\\]\\]\n  - \\[nums\\[2\\], nums\\[3\\]\\]\n- When combined with `nums[1]`, the valid subsequences are:\n  - \\[nums\\[1\\]\\]\n  - \\[nums\\[1\\], nums\\[2\\]\\]\n  - \\[nums\\[1\\], nums\\[3\\]\\]\n  - \\[nums\\[1\\], nums\\[2\\], nums\\[3\\]\\]\n- We have considered all the valid subsequences containing `nums[1]`, so increment `left` by 1 (`left += 1`).\n    \n\n**Step 4: left = 2, right = 3**\nnums\\[2\\] + nums\\[3\\] = 3 + 5 > 6\n- There are no valid subsequences that take `nums[2]` as the minimum and `nums[3]` as the maximum. So, decrement `right` by 1 (`right -= 1`).\n\n**Step 5: left = 2, right = 2**\nnums\\[2\\] + nums\\[2\\] = 3 + 3 <= 6\n\n- Always pick `nums[2]`\n- Consider all subsequences from elements in `nums[3..2]`:\n  - \\[\\]\n- When combined with `nums[2]`, the valid subsequences are:\n  - \\[nums\\[2\\]\\]\n- We have considered all the valid subsequences containing `nums[2]`, so increment `left` by 1 (`left += 1`).\n    \n\n**End of Program**
['Two Pointers', 'Python3']