To Find Number of Subsequences That Satisfy the Given Sum Condition
Approach\nFirstly sort the given array. Now set a right pointer to n-1 and left pointer to 0. Now check if nums[left] +nums[right] >target. This is because afte
# Approach\nFirstly sort the given array. Now set a right pointer to n-1 and left pointer to 0. Now check if nums[left] +nums[right] >target. This is because after sorting the smallest element will at left and largest element is on the right. If the sum is greater than target decrease the right pointer. If the sum is less than or equal to target add it to answer as ans+=(2^(right-left))%mod. Example if the right pointer is on 2nd index and left pointer on the 0th index then the total number of elements is 2-0+1=3 and the total number of subsequences possible is 2^2=4 of (2^(right-left)) %mod. Then increase the left pointer by one. Repeat this step until left pointer is smaller or equal to right pointer. This while loop will run in O(n) time complexity but we had sort the array in the beginning so the overall time complexity of the entire program will be O(nlogn).\n# Complexity\n- Time complexity:\nO(nlogn) for sorting\n\n- Space complexity:\nO(1)\n\n# Code\n```\nclass Solution {\npublic:\n    int numSubseq(vector<int>& nums, int target) {\n        int mod=1e9+7;\n        int ans=0;\n        int n=nums.size();\n        int left=0,right=n-1;\n        sort(nums.begin(),nums.end());\n        vector<int> pow(n,1);\n        for(int i=1;i<n;i++)\n        {\n            pow[i]=pow[i-1]*2%mod;\n        }\n        while(left<=right)\n        {\n            if((nums[left]+nums[right])>target)\n            {\n                right-=1;\n            }\n            else\n            {\n                ans=(ans+(pow[right-left]%mod))%mod;\n                left+=1;\n            }\n        }\n        return ans%mod;\n    }\n};\n```
['Array', 'Two Pointers', 'Binary Search', 'Sorting', 'C++']