[ C++ ] [ Dynamic Programming ] [ DP + Binary Search ]
Code\n\nclass Solution {\npublic:\n    int numSubseq(vector<int>& nums, int target) {\n        sort(nums.begin(), nums.end());\n        int n = nums.size();\n  
# Code\n```\nclass Solution {\npublic:\n    int numSubseq(vector<int>& nums, int target) {\n        sort(nums.begin(), nums.end());\n        int n = nums.size();\n        long res = 0;\n        int k = 1\'000\'000\'007;\n        vector<long> dp(n + 1, 1);\n        for(int i = 1; i <= n; ++i){\n            dp[i] = (dp[i - 1] << 1) % k;\n        }\n        for(int i = 0, j = n - 1; i < n; ++i){\n            while(j >= i && nums[i] + nums[j] > target) {\n                --j;\n            }\n            if(i > j) {\n                continue;\n            } \n            res = (res + dp[j - i]) % k; \n        }\n        return res;\n    }\n};\n```\n# UPD ( Binary Search to Speed Up the Process )\n```\nclass Solution {\npublic:\n    int numSubseq(vector<int>& nums, int target) {\n        sort(nums.begin(), nums.end());\n        int n = nums.size();\n        long res = 0;\n        int k = 1\'000\'000\'007;\n        vector<long> dp(n + 1, 1);\n        for(int i = 1; i <= n; ++i){\n            dp[i] = (dp[i - 1] << 1) % k;\n        }\n        int lo = 0, hi = n - 1;\n        while (lo <= hi) {\n            if (nums[lo] + nums[hi] > target) {\n                hi -= 1;\n            } \n            else {\n                (res += (dp[hi - lo])) %= k;\n                lo += 1;\n            }\n        }\n        return res;\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'C++']