You are given an array of integers nums and an integer target. Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal to target. Since the answer may be too large, return it mo

numSubseq.js

/**
 * Counts the number of non-empty subsequences such that
 * the minimum and maximum elements sum to <= target.
 *
 * @param {number[]} nums - Input array of integers
 * @param {number} target - Max allowed sum of min and max in a subsequence
 * @return {number} - Count of valid subsequences modulo 10^9 + 7
 */
var numSubseq = function(nums, target) {
    // Sort array to allow two-pointer traversal
    nums.sort((a, b) => a - b);
    
    const mod = 1e9 + 7;
    const n = nums.length;
    let res = 0;
    let left = 0;
    let right = n - 1;

    // Precompute powers of 2 up to n-1, since for a window of size k,
    // number of subsequences is 2^k (excluding the empty one)
    const pows = Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        pows[i] = (pows[i - 1] * 2) % mod;
    }

    // Two pointers: check combinations of min (nums[left]) and max (nums[right])
    while (left <= right) {
        if (nums[left] + nums[right] > target) {
            // Too big: try a smaller max element
            right--;
        } else {
            // All subsets between left and right are valid with nums[left] as min
            res = (res + pows[right - left]) % mod;
            left++;
        }
    }

    return res;
};