Number of Subsequences That Satisfy the Given Sum Condition
Description
You are given an array of integers nums and an integer target.
Your task is to count how many non-empty subsequences of nums satisfy the following condition: when you take the minimum element and the maximum element of that subsequence and add them together, their sum must be less than or equal to target.
A subsequence is any selection of elements from the array (not necessarily contiguous) that preserves the original relative order. For example, given [3, 5, 6], the subsequences include [3], [5], [6], [3, 5], [3, 6], [5, 6], and [3, 5, 6].
Since the answer can be very large, return it modulo 10^9 + 7.
Examples
Example 1
Input: nums = [3, 5, 6, 7], target = 9
Output: 4
Explanation: There are 4 valid subsequences:
- [3] → min = 3, max = 3, sum = 6 ≤ 9 ✓
- [3, 5] → min = 3, max = 5, sum = 8 ≤ 9 ✓
- [3, 6] → min = 3, max = 6, sum = 9 ≤ 9 ✓
- [3, 5, 6] → min = 3, max = 6, sum = 9 ≤ 9 ✓
All other subsequences have min + max exceeding 9. For instance, [3, 7] has min + max = 10 > 9.
Example 2
Input: nums = [3, 3, 6, 8], target = 10
Output: 6
Explanation: The array can contain duplicate values. The 6 valid subsequences are:
- [3] (first occurrence) → 3 + 3 = 6 ≤ 10 ✓
- [3] (second occurrence) → 3 + 3 = 6 ≤ 10 ✓
- [3, 3] → 3 + 3 = 6 ≤ 10 ✓
- [3, 6] (using first 3) → 3 + 6 = 9 ≤ 10 ✓
- [3, 6] (using second 3) → 3 + 6 = 9 ≤ 10 ✓
- [3, 3, 6] → 3 + 6 = 9 ≤ 10 ✓
Example 3
Input: nums = [2, 3, 3, 4, 6, 7], target = 12
Output: 61
Explanation: There are 63 total non-empty subsequences of an array of length 6. Only 2 of them are invalid: [6, 7] (min + max = 13 > 12) and [7] (min + max = 14 > 12). So the answer is 63 - 2 = 61.
Constraints
- 1 ≤ nums.length ≤ 10^5
- 1 ≤ nums[i] ≤ 10^6
- 1 ≤ target ≤ 10^6
Editorial
Brute Force
Intuition
The most direct way to solve this problem is to simply enumerate every possible non-empty subsequence of the array, and for each one, check whether the sum of its minimum and maximum elements is within the target.
Think of it like being in a candy store with a rule: you can pick any combination of candies from the shelf, but the cheapest candy plus the most expensive candy in your selection must cost no more than your budget. The brute force approach is to literally try every possible combination, check the cheapest and most expensive in each, and count how many combinations stay within budget.
For an array of length n, there are 2^n - 1 non-empty subsequences. We can generate them using recursion: at each element, we either include it in our current subsequence or skip it. Once we reach the end of the array, we check whether the current subsequence satisfies the condition.
Step-by-Step Explanation
Let's trace through with nums = [3, 5, 6, 7], target = 9.
We enumerate all 2^4 - 1 = 15 non-empty subsequences and check each:
Single elements (size 1):
- Step 1: Subsequence {3} → min = 3, max = 3, sum = 6. Is 6 ≤ 9? Yes ✓ (count = 1)
- Step 2: Subsequence {5} → min = 5, max = 5, sum = 10. Is 10 ≤ 9? No ✗
- Step 3: Subsequence {6} → min = 6, max = 6, sum = 12. Is 12 ≤ 9? No ✗
- Step 4: Subsequence {7} → min = 7, max = 7, sum = 14. Is 14 ≤ 9? No ✗
Pairs (size 2):
- Step 5: Subsequence {3, 5} → min = 3, max = 5, sum = 8. Is 8 ≤ 9? Yes ✓ (count = 2)
- Step 6: Subsequence {3, 6} → min = 3, max = 6, sum = 9. Is 9 ≤ 9? Yes ✓ (count = 3)
- Step 7: Subsequence {3, 7} → min = 3, max = 7, sum = 10. Is 10 ≤ 9? No ✗
- Step 8: Subsequence {5, 6} → min = 5, max = 6, sum = 11. Is 11 ≤ 9? No ✗
- Step 9: Subsequence {5, 7} → min = 5, max = 7, sum = 12. Is 12 ≤ 9? No ✗
- Step 10: Subsequence {6, 7} → min = 6, max = 7, sum = 13. Is 13 ≤ 9? No ✗
Triples (size 3):
- Step 11: Subsequence {3, 5, 6} → min = 3, max = 6, sum = 9. Is 9 ≤ 9? Yes ✓ (count = 4)
- Step 12: Subsequence {3, 5, 7} → min = 3, max = 7, sum = 10. Is 10 ≤ 9? No ✗
- Step 13: Subsequence {3, 6, 7} → min = 3, max = 7, sum = 10. Is 10 ≤ 9? No ✗
- Step 14: Subsequence {5, 6, 7} → min = 5, max = 7, sum = 12. Is 12 ≤ 9? No ✗
Full array (size 4):
- Step 15: Subsequence {3, 5, 6, 7} → min = 3, max = 7, sum = 10. Is 10 ≤ 9? No ✗
Result: count = 4. We checked all 15 subsequences and found exactly 4 that satisfy the condition.
Notice a key pattern: every valid subsequence contains 3 as its minimum. Once the minimum exceeds 4 (since 5 + 5 = 10 > 9), no subsequence starting from that element can be valid.
Algorithm
- Use recursion to generate all possible non-empty subsequences of the array
- At each index, make two choices: include the current element or skip it
- Track the current minimum and maximum as elements are added
- When the end of the array is reached with a non-empty subsequence, check if min + max ≤ target
- If the condition is satisfied, increment the count (modulo 10^9 + 7)
- Return the total count after exploring all subsequences
Code
class Solution {
public:
int numSubseq(vector<int>& nums, int target) {
int MOD = 1e9 + 7;
int n = nums.size();
int count = 0;
function<void(int, int, int, int)> generate =
[&](int idx, int curMin, int curMax, int size) {
if (idx == n) {
if (size > 0 && curMin + curMax <= target) {
count = (count + 1) % MOD;
}
return;
}
// Skip current element
generate(idx + 1, curMin, curMax, size);
// Include current element
int newMin = size > 0 ? min(curMin, nums[idx]) : nums[idx];
int newMax = size > 0 ? max(curMax, nums[idx]) : nums[idx];
generate(idx + 1, newMin, newMax, size + 1);
};
generate(0, INT_MAX, INT_MIN, 0);
return count;
}
};class Solution:
def numSubseq(self, nums: list[int], target: int) -> int:
MOD = 10**9 + 7
n = len(nums)
count = 0
def generate(idx, cur_min, cur_max, size):
nonlocal count
if idx == n:
if size > 0 and cur_min + cur_max <= target:
count = (count + 1) % MOD
return
# Skip current element
generate(idx + 1, cur_min, cur_max, size)
# Include current element
new_min = min(cur_min, nums[idx]) if size > 0 else nums[idx]
new_max = max(cur_max, nums[idx]) if size > 0 else nums[idx]
generate(idx + 1, new_min, new_max, size + 1)
generate(0, float('inf'), float('-inf'), 0)
return countclass Solution {
private int count = 0;
private static final int MOD = 1_000_000_007;
public int numSubseq(int[] nums, int target) {
count = 0;
generate(nums, 0, Integer.MAX_VALUE, Integer.MIN_VALUE, 0, target);
return count;
}
private void generate(int[] nums, int idx, int curMin, int curMax,
int size, int target) {
if (idx == nums.length) {
if (size > 0 && curMin + curMax <= target) {
count = (count + 1) % MOD;
}
return;
}
// Skip current element
generate(nums, idx + 1, curMin, curMax, size, target);
// Include current element
int newMin = size > 0 ? Math.min(curMin, nums[idx]) : nums[idx];
int newMax = size > 0 ? Math.max(curMax, nums[idx]) : nums[idx];
generate(nums, idx + 1, newMin, newMax, size + 1, target);
}
}Complexity Analysis
Time Complexity: O(2^n)
At each of the n elements, we make two recursive calls (include or exclude). This creates a binary recursion tree with 2^n leaf nodes. Each leaf does O(1) work to check the condition. For n = 10^5, 2^(10^5) is an astronomically large number — far beyond any computer's capability.
Space Complexity: O(n)
The recursion depth is at most n (one level per array element). Each stack frame stores a constant number of variables (index, curMin, curMax, size), so the total space used by the call stack is O(n).
Why This Approach Is Not Efficient
The brute force approach generates all 2^n subsequences, which is catastrophically slow. With n up to 10^5, even 2^20 ≈ 10^6 is barely manageable, and 2^(10^5) has over 30,000 digits — it is impossible to enumerate.
The fundamental issue is that we treat every subsequence as independent, ignoring the structure that could let us count valid subsequences in bulk.
Key insight that unlocks improvement: In any subsequence, only the minimum and maximum values matter for our condition — the elements in between are irrelevant to the check. If we could efficiently determine, for a given minimum, how far the maximum can go, we could count all valid subsequences at once using combinatorics (powers of 2) instead of enumerating them one by one.
Second key insight: Sorting the array does not change which multisets of values can form subsequences — it only changes their indices. After sorting, the minimum of any contiguous range is the leftmost element, and the maximum is the rightmost. This makes it easy to reason about valid ranges.
Better Approach - Sorting with Linear Search
Intuition
Instead of generating every subsequence, we exploit the fact that sorting the array lets us quickly identify valid ranges.
After sorting, consider fixing element nums[i] as the minimum of our subsequence. We need to find the rightmost index j such that nums[i] + nums[j] ≤ target. Since the array is sorted, every element between indices i and j has a value between nums[i] and nums[j], so any subsequence we form from this range will have its min at nums[i] and max at most nums[j] — satisfying our condition.
How many such subsequences exist? We must include nums[i] (the minimum). For each of the j - i elements at indices i+1 through j, we have two choices: include it or exclude it. This gives exactly 2^(j - i) valid subsequences for this fixed minimum.
In this approach, for each i, we linearly scan from the right end of the array to find the rightmost valid j. We precompute powers of 2 modulo 10^9 + 7 to avoid recomputation.
Step-by-Step Explanation
Let's trace through with nums = [3, 5, 6, 7], target = 9.
Preprocessing: Sort the array → [3, 5, 6, 7] (already sorted). Precompute pow2 = [1, 2, 4, 8].
Step 1: Set i = 0 (minimum candidate = 3). Start scanning from j = 3.
Step 2: Check j = 3: nums[0] + nums[3] = 3 + 7 = 10. Is 10 ≤ 9? No. The element at j = 3 is too large. Decrement j.
Step 3: Check j = 2: nums[0] + nums[2] = 3 + 6 = 9. Is 9 ≤ 9? Yes! We found the rightmost valid j for i = 0.
Step 4: Count subsequences for range [0, 2]: pow2[2 - 0] = pow2[2] = 4. These 4 subsequences are {3}, {3,5}, {3,6}, {3,5,6}. Add 4 to count. count = 4.
Step 5: Move to i = 1 (minimum candidate = 5). Start scanning from j = 3.
Step 6: Check j = 3: nums[1] + nums[3] = 5 + 7 = 12 > 9. Too large. Decrement j to 2.
Step 7: Check j = 2: nums[1] + nums[2] = 5 + 6 = 11 > 9. Still too large. Decrement j to 1.
Step 8: Check j = 1: nums[1] + nums[1] = 5 + 5 = 10 > 9. Even a single-element subsequence {5} fails. j goes below i. No valid subsequences for minimum = 5.
Step 9: Move to i = 2 (minimum candidate = 6). Check: nums[2] * 2 = 12 > 9. Even {6} alone fails the condition. Early termination — all remaining elements will also fail.
Result: count = 4.
Sorting with Linear Search — Finding Valid Ranges — For each minimum candidate (i), we scan from the right to find the farthest valid maximum (j), then count all 2^(j-i) subsequences in that range.
Algorithm
- Sort the array in ascending order
- Precompute an array pow2 where pow2[k] = 2^k mod (10^9 + 7)
- For each index i from 0 to n - 1:
- If nums[i] × 2 > target, break (early termination)
- Set j = n - 1
- While j ≥ i and nums[i] + nums[j] > target, decrement j
- If j ≥ i, add pow2[j - i] to the count
- Return count modulo 10^9 + 7
Code
class Solution {
public:
int numSubseq(vector<int>& nums, int target) {
int MOD = 1e9 + 7;
int n = nums.size();
sort(nums.begin(), nums.end());
vector<long long> pow2(n, 1);
for (int i = 1; i < n; i++) {
pow2[i] = pow2[i - 1] * 2 % MOD;
}
long long count = 0;
for (int i = 0; i < n; i++) {
if ((long long)nums[i] * 2 > target) break;
int j = n - 1;
while (j >= i && nums[i] + nums[j] > target) {
j--;
}
if (j >= i) {
count = (count + pow2[j - i]) % MOD;
}
}
return (int)count;
}
};class Solution:
def numSubseq(self, nums: list[int], target: int) -> int:
MOD = 10**9 + 7
nums.sort()
n = len(nums)
pow2 = [1] * n
for i in range(1, n):
pow2[i] = pow2[i - 1] * 2 % MOD
count = 0
for i in range(n):
if nums[i] * 2 > target:
break
j = n - 1
while j >= i and nums[i] + nums[j] > target:
j -= 1
if j >= i:
count = (count + pow2[j - i]) % MOD
return countclass Solution {
public int numSubseq(int[] nums, int target) {
int MOD = 1_000_000_007;
int n = nums.length;
Arrays.sort(nums);
long[] pow2 = new long[n];
pow2[0] = 1;
for (int i = 1; i < n; i++) {
pow2[i] = pow2[i - 1] * 2 % MOD;
}
long count = 0;
for (int i = 0; i < n; i++) {
if ((long) nums[i] * 2 > target) break;
int j = n - 1;
while (j >= i && nums[i] + nums[j] > target) {
j--;
}
if (j >= i) {
count = (count + pow2[j - i]) % MOD;
}
}
return (int) count;
}
}Complexity Analysis
Time Complexity: O(n²)
Sorting takes O(n log n). The main loop runs for each index i from 0 to n - 1. For each i, the inner while loop can scan up to n - 1 elements in the worst case. Since the scan restarts from j = n - 1 for every i, the total work across all iterations can reach O(n²). For example, with a sorted array [1, 2, 3, ..., n] and target = n, each i causes j to scan approximately (n - i) / 2 positions, summing to O(n²). The overall complexity is O(n log n + n²) = O(n²).
Space Complexity: O(n)
The pow2 array stores n precomputed powers of 2, requiring O(n) space. Sorting may use O(log n) to O(n) auxiliary space depending on the implementation. All other variables are O(1).
Why This Approach Is Not Efficient
While the sorting insight is powerful, the linear search for each i makes the approach O(n²) in the worst case. With n up to 10^5, that is 10^10 operations — far too slow for typical time limits of around 10^8 operations per second.
The root cause of the inefficiency is redundant scanning: for each new minimum candidate i, we restart the scan from j = n - 1. But notice something crucial — as i increases (moving right), the valid range for j can only shrink (the rightmost valid j can only decrease or stay the same). This is because nums[i] increases when i increases (array is sorted), so target - nums[i] decreases, meaning the maximum allowed value for nums[j] decreases.
This monotonic relationship between i and j is the hallmark of a two-pointer pattern: one pointer moves right while the other moves left, and neither ever backtracks. This eliminates the redundant re-scanning and reduces the scan from O(n²) to O(n).
Optimal Approach - Sorting with Two Pointers
Intuition
Building on the sorting insight from the previous approach, we replace the redundant linear scan with a two-pointer technique.
After sorting, place a left pointer at the start and a right pointer at the end of the array. These represent the current minimum and maximum candidates.
-
If
nums[left] + nums[right] ≤ target, the current pair is valid. Every subsequence that includesnums[left]as the minimum and picks any subset of elements betweenleft + 1andrightis valid. That is 2^(right - left) subsequences. We count them all and advanceleftto consider the next minimum. -
If
nums[left] + nums[right] > target, the maximum is too large. We decrementrightto try a smaller maximum.
The key insight that makes this O(n) (after sorting) is that right never needs to move back to the right. As left increases, nums[left] increases, which means the valid range for right can only shrink or stay the same — it never grows. So each pointer moves at most n times, giving O(n) total pointer movements.
Think of it as two people walking toward each other in a hallway. One starts at the left wall (smallest values), the other at the right wall (largest values). If the right person's number is too large, they step left. If the pair works, the left person counts all valid groups and steps right. They meet in the middle and the process is complete — never backtracking.
Step-by-Step Explanation
Let's trace through with nums = [3, 5, 6, 7], target = 9.
Preprocessing: Sort → [3, 5, 6, 7]. Precompute pow2 = [1, 2, 4, 8].
Step 1: Initialize left = 0, right = 3. count = 0.
Step 2: Check nums[0] + nums[3] = 3 + 7 = 10. Is 10 ≤ 9? No — the right element is too large.
Step 3: Decrement right to 2. Now right points to value 6.
Step 4: Check nums[0] + nums[2] = 3 + 6 = 9. Is 9 ≤ 9? Yes! Valid pair found.
Step 5: Count subsequences: pow2[right - left] = pow2[2 - 0] = pow2[2] = 4. These are {3}, {3,5}, {3,6}, {3,5,6}. count = 0 + 4 = 4. Advance left to 1.
Step 6: Check nums[1] + nums[2] = 5 + 6 = 11. Is 11 ≤ 9? No — right element is too large.
Step 7: Decrement right to 1. Now left = 1 and right = 1.
Step 8: Check nums[1] + nums[1] = 5 + 5 = 10. Is 10 ≤ 9? No — even a single element {5} fails.
Step 9: Decrement right to 0. Now left = 1 > right = 0, so the loop terminates.
Result: count = 4. The two pointers made only 4 moves total (left moved once, right moved three times), compared to the linear search which scanned 7 positions.
Two Pointers Converging — Count Valid Subsequences — Watch left and right pointers converge from opposite ends. When the sum is valid, we count all 2^(right-left) subsequences instantly and advance left. When too large, we shrink right.
Algorithm
- Sort the array in ascending order
- Precompute an array pow2 where pow2[k] = 2^k mod (10^9 + 7) for k = 0 to n - 1
- Initialize two pointers: left = 0, right = n - 1, and count = 0
- While left ≤ right:
- If nums[left] + nums[right] ≤ target:
- Add pow2[right - left] to count (modulo 10^9 + 7)
- Increment left (try a larger minimum)
- Else:
- Decrement right (try a smaller maximum)
- If nums[left] + nums[right] ≤ target:
- Return count
Code
class Solution {
public:
int numSubseq(vector<int>& nums, int target) {
int MOD = 1e9 + 7;
int n = nums.size();
sort(nums.begin(), nums.end());
vector<long long> pow2(n, 1);
for (int i = 1; i < n; i++) {
pow2[i] = pow2[i - 1] * 2 % MOD;
}
long long count = 0;
int left = 0, right = n - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
count = (count + pow2[right - left]) % MOD;
left++;
} else {
right--;
}
}
return (int)count;
}
};class Solution:
def numSubseq(self, nums: list[int], target: int) -> int:
MOD = 10**9 + 7
nums.sort()
n = len(nums)
pow2 = [1] * n
for i in range(1, n):
pow2[i] = pow2[i - 1] * 2 % MOD
count = 0
left, right = 0, n - 1
while left <= right:
if nums[left] + nums[right] <= target:
count = (count + pow2[right - left]) % MOD
left += 1
else:
right -= 1
return countclass Solution {
public int numSubseq(int[] nums, int target) {
int MOD = 1_000_000_007;
int n = nums.length;
Arrays.sort(nums);
long[] pow2 = new long[n];
pow2[0] = 1;
for (int i = 1; i < n; i++) {
pow2[i] = pow2[i - 1] * 2 % MOD;
}
long count = 0;
int left = 0, right = n - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
count = (count + pow2[right - left]) % MOD;
left++;
} else {
right--;
}
}
return (int) count;
}
}Complexity Analysis
Time Complexity: O(n log n)
Sorting the array takes O(n log n). Precomputing the pow2 array takes O(n). The two-pointer scan takes O(n) because each pointer moves at most n positions total — the left pointer can only move right, and the right pointer can only move left, so the combined number of moves is at most 2n. The dominant term is the sort: O(n log n).
Space Complexity: O(n)
The pow2 array stores n precomputed values, requiring O(n) space. The sorting step may use O(log n) to O(n) auxiliary space depending on the language and implementation. All pointer variables and the count use O(1) space. Overall: O(n).