C++ | Two Pointer Solution | O(nlogn) | Explained
Approach\n1. Sort the given nums array.\n2. For every index i from 0 to n-1 find the index j of largest number.\n3. The number of valid subsequences are 2^(j - 
Approach\n1. Sort the given nums array.\n2. For every index i from 0 to n-1 find the index j of largest number.\n3. The number of valid subsequences are 2^(j - i)\n\nI have stored the values from 2^0 to 2^(n-1) to avoid repeated computations.\n\n```\n    int numSubseq(vector<int>& nums, int target) {\n        \n        int mod = 1000000007;\n        \n        //sort the given array\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n        \n        //store 2^power to decrease computations\n        vector<int> power = {1};\n        for(int i = power.size(); i < n; i++){\n            power.push_back((power.back() << 1)%mod);\n        }\n        \n        //store the result in res\n        int res = 0;\n        \n        //Initialize a pointer j pointing to the last element\n        int j = n - 1;\n        for(int i = 0; i < n; i++){\n            \n            // Decrement j until condition satisfies\n            while(nums[i] + nums[j] > target && i < j) j--;\n            \n            // Add 2^(j - i) to the result\n            if(nums[i] + nums[j] <= target){\n                res = (res%mod + power[j - i]%mod)%mod;\n            }\n        }\n        \n        return res;\n    }\n```
[]