Number of Subsequences That Satisfy the Given Sum Condition: Sort and Two Pointers

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 of the subsequence is less than or equal to target. Since the answer may be large, return it modulo 10^9 + 7.

This is LeetCode 1498: Number of Subsequences That Satisfy the Given Sum Condition, and it is one of the cleanest examples of combining sorting with two pointers to count combinatorial structures efficiently.

Why this problem matters

Counting subsequences sounds like it should require dynamic programming or backtracking, but this problem has a beautiful shortcut. The constraint only involves the minimum and maximum of the subsequence, not the sum of all elements. That means the order of elements between the min and max does not matter, and sorting the array does not change the answer.

This insight, that sorting preserves subsequence validity when the constraint only depends on extreme values, appears in many problems. Once you see it here, you will recognize it in "Number of Subsequences" variants, "Count Pairs" problems, and any question where you need to reason about min/max over subsets.

The key insight

After sorting the array, consider a pair of indices left and right. If nums[left] + nums[right] is at most target, then nums[left] is the minimum and nums[right] is the maximum of any subsequence that includes both of them and only picks elements from the range [left, right].

Here is the combinatorial argument: you must include nums[left] (it is the min). You may or may not include nums[right] (if left equals right, you include it; otherwise it is up to you). Every element strictly between left and right can either be included or excluded. That gives you 2^(right - left) valid subsequences where nums[left] is the minimum.

By fixing the left pointer and finding the farthest right pointer that satisfies the condition, you count all subsequences with that particular minimum in one shot. Then you move left forward and repeat.

The solution

def num_subseq(nums: list[int], target: int) -> int:
    MOD = 10**9 + 7
    nums.sort()
    n = len(nums)
    power = [1] * n
    for i in range(1, n):
        power[i] = (power[i - 1] * 2) % MOD

    result = 0
    left, right = 0, n - 1

    while left <= right:
        if nums[left] + nums[right] <= target:
            result = (result + power[right - left]) % MOD
            left += 1
        else:
            right -= 1

    return result

Let's walk through what each piece does.

First, we sort the array. Sorting lets us use two pointers: the left pointer always points to the minimum element of the subsequences we are counting, and the right pointer marks the farthest element whose value, combined with the left element, still satisfies the condition.

The power array precomputes powers of 2 modulo 10^9 + 7. We need power[k] to represent the number of subsets of k elements (each element is either included or excluded). Precomputing avoids calling pow() repeatedly.

The two-pointer loop works like this: if nums[left] + nums[right] is at most target, then every subsequence that must include nums[left] and only picks from nums[left..right] is valid. There are 2^(right - left) such subsequences (the left element is always included, the remaining right - left elements are each optional). We add that count and move left forward to count subsequences with the next minimum.

If the sum exceeds the target, the right element is too large. We move right inward to try a smaller maximum.

Visual walkthrough

Let's trace through nums = [3, 5, 6, 7] with target = 9. After sorting (already sorted), we use two pointers to count valid subsequences.

The two pointers converge toward each other. Each time the sum is valid, we count all 2^(right - left) subsequences with that left element as the minimum, then advance left. Each time the sum is too large, we shrink right. The pointers meet in the middle, and we have our answer: 4 subsequences.

Complexity analysis

Time is O(n log n) dominated by the sort. The two-pointer traversal is O(n) since each pointer moves at most n times total. Precomputing powers is also O(n).

Space is O(n) for the precomputed powers array. If you use Python's built-in pow(2, k, MOD) instead, you can reduce space to O(1) at the cost of O(log k) per call, but the precomputed approach is faster in practice.

The building blocks

1. Sort and two-pointer framework

The pattern of sorting an array and using two pointers to find pairs that satisfy a condition:

nums.sort()
left, right = 0, len(nums) - 1

while left <= right:
    if nums[left] + nums[right] <= target:
        left += 1
    else:
        right -= 1

This is the same skeleton used in Two Sum II, 3Sum, and Container With Most Water. The key property is monotonicity: if the sum is too large, decreasing right can only decrease the sum, and if the sum is small enough, increasing left explores new possibilities. Here we add a counting step before moving left, but the structure is identical.

2. Counting with powers of 2

The pattern of precomputing modular powers for combinatorial counting:

MOD = 10**9 + 7
power = [1] * n
for i in range(1, n):
    power[i] = (power[i - 1] * 2) % MOD

When you need to count subsets, the number of subsets of a set with k elements is 2^k. Precomputing these values avoids repeated exponentiation. You will see this pattern in problems involving subset counting, binary strings, and combinatorics under modular arithmetic. The recurrence power[i] = power[i-1] * 2 is simple, but remembering to apply the modulo at each step prevents overflow.

Edge cases

• All elements doubled exceed target: if nums[0] + nums[0] > target after sorting, no single element satisfies the condition. Return 0.
• Single element: if the array has one element and 2 * nums[0] is at most target, the answer is 1.
• All pairs valid: if nums[0] + nums[n-1] is at most target, every non-empty subsequence is valid. The answer is 2^n - 1 mod 10^9 + 7.
• Large arrays: with n up to 100,000, the O(n log n) approach handles the constraints comfortably. The precomputed powers array avoids TLE from repeated modular exponentiation.
• Duplicate elements: duplicates do not require special handling. The two-pointer logic counts each index independently, so duplicate values at different indices produce distinct subsequences.

From understanding to recall

You have seen how sorting transforms a combinatorial counting problem into a two-pointer sweep, and how precomputed powers of 2 give you instant subset counts. The logic is elegant, but the details matter under pressure. Do you remember to precompute powers? Do you add power[right - left] or power[right - left - 1]? Do you move left or right after counting?

These are recall gaps, not understanding gaps. Spaced repetition closes them. You practice writing the sort, the power precomputation, and the two-pointer loop from memory at increasing intervals. After a few rounds, the pattern becomes automatic. You see "count subsequences where min + max satisfies a condition" and the template flows out without hesitation.

Related posts

• Two Sum II - Input Array Is Sorted - The foundational two-pointer problem on a sorted array that this technique builds upon
• 3Sum Closest - Extends two pointers to three elements, using the same sorted-array convergence strategy
• Subarray Product Less Than K - Another sliding window counting problem where you count valid subarrays as you expand and contract a window

CodeBricks breaks this problem into its sorting, two-pointer, and modular exponentiation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a counting problem shows up in your interview, you do not fumble with off-by-one errors. You just write it.