1498. Number of Subsequences That Satisfy the Given Sum Condition

First understand the the question..

Return non-empty subsequences

Sum of the min and max element on this less or equal to target

return module 10^9 + 7

Brute Force approach (Generating all subsequences)

A straightforward idea is to generate all possible subsequences, then count how many have a minimum plus maximum sum less than or equal to the target.

However, this takes 2^n time, which quickly exceeds time and memory limits for large inputs. In short, it’s not practical for LeetCode.

Basic steps:

1. Sort nums in ascending order.

2. Generate all subsequences.

3. For each, check if min + max ≤ target.

4. Count the valid ones.

Code of generate all subsequences in c++

void subsequence_generate_with_ans_count(vector<int> nums, vector<int> v, int i, int n, int target, int &count) {
    if( i == n ) {
        int sum = 0;
        if(v.size() > 1) {
            sum = v[0] + v[v.size() - 1];
        }    else if(v.size() == 1) {
                sum = v[0] + v[0];
        }    else {
                return;
        }
        if( sum <= target) {
           (*count)++;  
        }
        return;    
    }
    vector<int> temp = v;
    temp.push_back(nums[i]);
    subsequence_generate_with_ans_count(nums, temp, i+1, n, target, count);
    subsequence_generate_with_ans_count(nums, v, i+1, n, target, count);
}

How this code works (based on your explanation)

1. Base case:

    if (i == n) { ... }
   

   When you reach the end of the array (i == n), you check the current subsequence v.

2. Sum calculation:

    if (v.size() > 1) {
        sum = v[0] + v[v.size() - 1];
    } else if (v.size() == 1) {
        sum = v[0] + v[0];
    } else {
        return;
    }
   

   • If the subsequence has more than one element, you sum the first and last element (assuming nums is sorted).

   • If it has one element, you add it to itself.

   • If it’s empty, you just return without doing anything.

3. Count valid subsequences:

    if (sum <= target) {
        (*count)++;
    }
   

   If the sum of min + max is within the target, you increment the counter.

4. Generate all subsequences:

    subsequence_generate_with_ans_count(nums, temp, i+1, n, target, count);
    subsequence_generate_with_ans_count(nums, v, i+1, n, target, count);
   

   This is the classic subsequence pattern — for each element:

   • Include it (temp.push_back(nums[i]))

   • Or exclude it (call with v unchanged).

Two Pointer Approach

Here is the approach when the sum is greater then target reduce r by one, when sum is less then or equal to target increase the l by one

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {

        const int MOD = 1e9 + 7;
        // use two pointer approach
        // sort the vector
        sort(nums.begin(), nums.end());
        // then check with min value + max value by two pointer
        // when the sum is less then or equal to target calculate 2^(r - l) is the
        // number of subsequence from this range. Add all possible subsequence
        // by this process
        int l = 0;
        int r = nums.size() - 1;
        long long count = 0;

        while (l <= r) {
            int sum = nums[l] + nums[r];
            if (sum > target) {
                r--;
            } else {
                count = (count + my_pow(2, r - l, MOD)) % MOD;
                l++;
            }
        }

        return count;
    }

    long long my_pow(long long base, long long exp, long long mod) {
        long long result = 1;
        base %= mod;

        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return result;
    }
};

Time complexity of this code is 0(n log n)