Java - O(n log(n)) - Binary Search
\nIdea:\n\n1. Sort the array firstly, because of the binary search.\n2. Each time we fix a starting point, then use binary search to find the ending point\n3. o
\nIdea:\n\n1. Sort the array firstly, because of the binary search.\n2. Each time we fix a starting point, then use binary search to find the ending point\n3. once we got starting and endinng point, 2^(end-start) makes sense, because for each element we select or not to select\n\nTime Complexity: O(n log(n))\nSpace Complexity: O(n) // because of the powDP[], but I guess in Python, we can fulfill O(1)Space?\n\nTIPS for JAVA USERS:\nIt is impossible to use 2^n in Java when n is very large(overflow), but Python can. So we need to use DP-method to pre-calculate 2^n % 1e9+7\n\n```\nclass Solution {\n    public int numSubseq(int[] nums, int target) {\n        Arrays.sort(nums);\n        int res=0;\n        int toMod=(int)1e9+7;\n        //It is impossible to use 2^n in Java when n is very large, but Python can\n        //So we need to use DP-method to pre-calculate 2^n % 1e9+7\n        int[] powDP = new int[nums.length];\n        powDP[0] = 1;\n        for(int i=1; i<powDP.length; i++) powDP[i] = (powDP[i-1]*2)%toMod;\n        //each time we fix a starting point\n        for(int start=0; start<nums.length; start++){\n            //like two-sum, we use binary search to find the nums[end] <= target-nums[start]\n            //in other word, we use binary search to find the ending point\n            int l=start, r=nums.length-1;\n            //"end" is to memorize the largest element satisfying our requirement\n            //and its initial value -1 is important as well\n            int end = -1;\n            while(l<=r){\n                int mid = l+(r-l)/2;\n                if(nums[start]+nums[mid]<=target){\n                    l=mid+1;\n                    end=mid;\n                }\n                else r=mid-1;\n            }\n            //so we\'ve got starting and ending points\n            \n            //we have to consider a situation that we didn\'t find an element satisfying(nums[end] <= target-nums[start])\n            //Then we can stop the iteration and return the result\n            if(end==-1) break;\n            res = (res + powDP[end-start])%toMod;\n        }\n        \n        return res;\n    }\n}\n```
[]