# 1498. Number of Subsequences That Satisfy the Given Sum Condition
###### tags: `Leetcode` `FaceBook` `Medium` `Binary Search` `Two Sum`
## 思路 $O(NlogN)$ $O(N)$
Binary search
先排序，然后对于每一个值，以它为起点(minimum value)，binary search找maximum value
由于这里要计算2的n次方，很有可能会overflow，所以需要先把可能的结果用一个dp array存下来，这样才能在计算的过程中就算mod

这里解释一下为什么是```result+powerDP[start-1-idx]``` 因为$powerDP[i]$ 里面包含的是一共i+1个数，一定包含第一个数，也就是只能决定后i个数要不要 一共有几种可能，而我们要算排列组合的阵列是从idx到start-1，所以要写成那样
## Code

class Solution {
    public int numSubseq(int[] nums, int target) {
        int result = 0;
        Arrays.sort(nums);
        int idx = 0;
        int[] powerDP = new int[nums.length];
        powerDP[0] = 1;
        int mod = 1000000007;
        for(int i = 1;i < nums.length;i++){
            powerDP[i] = (powerDP[i-1]*2)%mod;
        }
        while(idx < nums.length){
            int smaller = nums[idx];
            int start = idx;
            int end = nums.length;
            if(smaller*2>target) break;
            while(start<end){
                int mid = start+(end-start)/2;
                if(nums[mid]<=target-smaller){
                    start = mid+1;
                }
                else{
                    end = mid;
                }
            }
            result = (result+powerDP[start-1-idx])%mod;
            idx++;
        }
        return result;
    }
}