# Number of Subsequences That Satisfy the Given Sum Condition
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition)
Canonical: https://scaleengineer.com/dsa/problems/number-of-subsequences-that-satisfy-the-given-sum-condition
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Turing](https://scaleengineer.com/companies/turing)
---
## Problem
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 **modulo** `109 + 7`.

**Example 1:**

**Input:** nums = [3,5,6,7], target = 9
**Output:** 4
**Explanation:** There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

**Example 2:**

**Input:** nums = [3,3,6,8], target = 10
**Output:** 6
**Explanation:** There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

**Example 3:**

**Input:** nums = [2,3,3,4,6,7], target = 12
**Output:** 61
**Explanation:** There are 63 non-empty subsequences, two of them do not satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 106`
* `1 <= target <= 106`

# Approaches
## Brute Force by Generating All Subsequences
This approach involves generating every possible non-empty subsequence of the input array `nums`. For each subsequence, we find its minimum and maximum elements and check if their sum is less than or equal to the `target`. If the condition is met, we increment a counter. This method is the most straightforward to conceptualize but is computationally infeasible for the given constraints.
**Time:** O(N * 2^N), where N is the length of `nums`. There are `2^N` subsequences, and for each one, finding the minimum and maximum elements takes O(K) time, where K is the length of the subsequence (up to N). · **Space:** O(N), where N is the length of `nums`. This space is used by the recursion stack and to store the current subsequence being built.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error on any reasonably sized input.
### Explanation
The core idea is to explore all possibilities. We can write a recursive function that, at each step, decides whether to include the current element in the subsequence or not. This builds a decision tree that covers all `2^n` possible subsequences. For each complete subsequence, we then perform a check.

```java
// This is a conceptual implementation and will time out.
class Solution {
    int count = 0;
    int target;
    int[] nums;
    final int MOD = 1_000_000_007;

    public int numSubseq(int[] nums, int target) {
        this.target = target;
        this.nums = nums;
        generateSubsequences(0, new java.util.ArrayList<>());
        return count;
    }

    private void generateSubsequences(int index, java.util.List<Integer> current) {
        if (index == nums.length) {
            if (!current.isEmpty()) {
                int min = Integer.MAX_VALUE;
                int max = Integer.MIN_VALUE;
                for (int num : current) {
                    min = Math.min(min, num);
                    max = Math.max(max, num);
                }
                if (min + max <= target) {
                    count = (count + 1) % MOD;
                }
            }
            return;
        }

        // Decision 1: Exclude nums[index]
        generateSubsequences(index + 1, current);

        // Decision 2: Include nums[index]
        current.add(nums[index]);
        generateSubsequences(index + 1, current);
        current.remove(current.size() - 1); // Backtrack
    }
}
```
This method is too slow because the number of subsequences grows exponentially with the size of the input array `nums`.
### Algorithm
- Initialize a counter `count` to 0.
- Generate all non-empty subsequences of `nums` using a recursive or iterative approach.
- For each generated subsequence:
  - Find its minimum element `min_val` and maximum element `max_val`.
  - If `min_val + max_val <= target`, increment `count`.
- Return `count` modulo `10^9 + 7`.

## Sorting and Binary Search
A more efficient approach starts by recognizing that the order of elements within a subsequence doesn't affect the min/max sum condition. By sorting the input array `nums`, we can simplify the problem. If we fix the minimum element of a subsequence, `nums[i]`, we only need to ensure the maximum element, `nums[j]`, satisfies `nums[i] + nums[j] <= target`. Since the array is sorted, we can use binary search to efficiently find the count of valid maximums for each chosen minimum.
**Time:** O(N log N). Sorting takes O(N log N). The main loop runs N times, with a binary search of O(log N) inside, contributing another O(N log N). · **Space:** O(N) to store the precomputed powers of 2. The space for sorting depends on the implementation, typically O(log N) or O(N).
**Pros:** Significantly more efficient than the brute-force approach.; Passes the time limits for the given constraints.
**Cons:** The overall time complexity is O(N log N), which can be slightly improved upon.
### Explanation
After sorting `nums`, we iterate through each element `nums[i]` and consider it as the fixed minimum of our subsequences. For this `nums[i]`, we need to find how many subsequences can be formed. The maximum element of any such subsequence, let's say `nums[k]`, must satisfy `nums[i] + nums[k] <= target`. This implies `nums[k] <= target - nums[i]`. We can find the rightmost element `nums[j]` that satisfies this condition using binary search. Any element between `nums[i]` and `nums[j]` can be included in the subsequence. If we fix `nums[i]` as the minimum, we can freely choose any subset of the elements `{nums[i+1], ..., nums[j]}`. There are `j-i` such elements, giving `2^(j-i)` possible subsequences. We sum these counts for each `i`.

To avoid recomputing powers of 2, we pre-calculate them and store them in an array.

```java
import java.util.Arrays;

class Solution {
    public int numSubseq(int[] nums, int target) {
        int n = nums.length;
        int MOD = 1_000_000_007;
        Arrays.sort(nums);

        long[] powers = new long[n];
        powers[0] = 1;
        for (int i = 1; i < n; i++) {
            powers[i] = (powers[i - 1] * 2) % MOD;
        }

        int count = 0;
        for (int i = 0; i < n; i++) {
            int searchVal = target - nums[i];
            int left = i, right = n - 1, j = -1;
            // Binary search for the rightmost index j <= searchVal
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] <= searchVal) {
                    j = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            if (j >= i) {
                count = (int)((count + powers[j - i]) % MOD);
            }
        }
        return count;
    }
}
```
### Algorithm
- Sort the input array `nums`.
- Precompute powers of 2 modulo `10^9 + 7` and store them in an array `powers`.
- Initialize a result counter `count` to 0.
- Iterate through the sorted array with an index `i` from `0` to `n-1`.
  - For each `nums[i]`, treat it as the minimum element of a subsequence.
  - Use binary search to find the largest index `j >= i` such that `nums[j] <= target - nums[i]`.
  - If such a `j` exists, it means any subsequence starting with `nums[i]` and containing elements from the range `nums[i+1]` to `nums[j]` is valid.
  - The number of such subsequences is `2^(j-i)`. Add `powers[j-i]` to the `count`.
- Return `count`.

## Sorting and Two Pointers
This is the most optimal approach. It builds upon the sorting idea but replaces the repeated binary searches with a more efficient two-pointer technique. After sorting `nums`, we use a `left` pointer for the minimum element and a `right` pointer for the maximum. Because the array is sorted, as `left` increases, the `right` pointer can only decrease or stay put, allowing for a single linear scan of the array.
**Time:** O(N log N), dominated by the initial sorting step. The subsequent two-pointer scan takes only O(N) time. · **Space:** O(N) to store the precomputed powers of 2. Sorting space is typically O(log N) or O(N).
**Pros:** Most efficient solution with an optimal time complexity.; The two-pointer scan is O(N), which is faster than the O(N log N) loop in the binary search approach.
**Cons:** The main bottleneck is the initial sorting step, which is hard to avoid for this problem.
### Explanation
We start by sorting `nums`. We initialize `left` to the start of the array and `right` to the end. The loop continues as long as `left <= right`.

If `nums[left] + nums[right] <= target`, we know that `nums[left]` can be the minimum of a valid subsequence. The maximum of this subsequence can be any element from `nums[left]` up to `nums[right]`. This is because if `nums[right]` works, any `nums[k]` with `k < right` will also work since `nums[k] <= nums[right]`. The subsequences are formed by taking `nums[left]` and any subset of the elements `{nums[left+1], ..., nums[right]}`. There are `right - left` such elements, so we can form `2^(right - left)` valid subsequences. We add this to our total count and then increment `left` because we have found all valid subsequences with `nums[left]` as the minimum.

If `nums[left] + nums[right] > target`, the sum is too large. To fix this, we must decrease the sum, which means we need a smaller maximum element. So, we decrement `right`.

This process efficiently counts all valid subsequences in a single pass after the initial sort.

```java
import java.util.Arrays;

class Solution {
    public int numSubseq(int[] nums, int target) {
        int n = nums.length;
        int MOD = 1_000_000_007;
        Arrays.sort(nums);

        long[] powers = new long[n + 1];
        powers[0] = 1;
        for (int i = 1; i <= n; i++) {
            powers[i] = (powers[i - 1] * 2) % MOD;
        }

        int count = 0;
        int left = 0;
        int right = n - 1;

        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                count = (int)((count + powers[right - left]) % MOD);
                left++;
            } else {
                right--;
            }
        }
        return count;
    }
}
```
### Algorithm
- Sort the input array `nums`.
- Precompute powers of 2 modulo `10^9 + 7`.
- Initialize two pointers, `left = 0` and `right = n-1`, and a `count = 0`.
- While `left <= right`:
  - If `nums[left] + nums[right] <= target`:
    - This pair is valid. `nums[left]` can be the minimum. The maximum can be any element from `nums[left]` to `nums[right]`.
    - The number of valid subsequences with `nums[left]` as the minimum is `2^(right - left)`.
    - Add this to `count`.
    - Since we've counted all subsequences with `nums[left]` as the minimum, we move to the next potential minimum: `left++`.
  - Else (`nums[left] + nums[right] > target`):
    - `nums[right]` is too large. We need a smaller maximum, so we decrement `right`.
- Return `count`.

# Solutions
### Java

```java
class Solution {
public
  int numSubseq(int[] nums, int target) {
    Arrays.sort(nums);
    final int mod = (int)1 e9 + 7;
    int n = nums.length;
    int[] f = new int[n + 1];
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
      f[i] = (f[i - 1] * 2) % mod;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (nums[i] * 2L > target) {
        break;
      }
      int j = search(nums, target - nums[i], i + 1) - 1;
      ans = (ans + f[j - i]) % mod;
    }
    return ans;
  }
private
  int search(int[] nums, int x, int left) {
    int right = nums.length;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[mid] > x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numSubseq(vector<int> &nums, int target) {
    sort(nums.begin(), nums.end());
    const int mod = 1e9 + 7;
    int n = nums.size();
    int f[n + 1];
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
      f[i] = (f[i - 1] * 2) % mod;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (nums[i] * 2L > target) {
        break;
      }
      int j = upper_bound(nums.begin() + i + 1, nums.end(), target - nums[i]) -
              nums.begin() - 1;
      ans = (ans + f[j - i]) % mod;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int: mod = 10 ** 9 + 7 nums . sort() n = len(nums) f = [1] + [0] * n for i in range(1, n + 1): f[i] = f[i - 1] * 2 % mod ans = 0 for i, x in enumerate(nums): if x * 2 > target: break j = bisect_right(nums, target - x, i + 1) - 1 ans = (ans + f[j - i]) % mod return ans

```