Description

Submission

class Solution {
    typedef long long ll;
    const ll M = 1e9+7;
    int mem[100005];
public:
    int numSubseq(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();

        mem[0] = 1;
        for(int i = 1; i < n; ++i) {
            mem[i] = (mem[i-1] << 1) % M;
        }
        
        ll ret = 0;
        for(auto it = nums.begin(); it != nums.end(); ++it) {
            auto up = upper_bound(nums.begin(), nums.end(), target-*it);
            if(up <= it) break;
            ret += mem[up-it-1];
            ret %= M;
        }
        
        return ret;
    }
};