> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/number-of-subsequences-that-satisfy-the-given-sum-condition.md).

# Number of Subsequences That Satisfy the Given Sum Condition

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 than `target`.

Since the answer may be too large, return it modulo 10^9 + 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 don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).
```

**Example 4:**

```
Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127
```

**Constraints:**

* `1 <= nums.length <= 10^5`
* `1 <= nums[i] <= 10^6`
* `1 <= target <= 10^6`

```java
class Solution {
    // In this question we only care about min, max of
    // a subsequence, thats why we can sort the array in starting.
    public int numSubseq(int[] nums, int target) {
        int n = nums.length;
        int mod = 1_000_000_007;
        // Record all 2 ^ n to save time
        int[] powerOfTwo = new int[n + 1];
        powerOfTwo[0] = 1;
        for (int i = 1; i <= n; ++i)
            powerOfTwo[i] = (powerOfTwo[i - 1] * 2) % mod;
        // Sorting part
        Arrays.sort(nums);
        // Try to use each number as the min number, fixing min number also makes sure
        // that min number alone will be a valid subsequence
        int ans = 0;
        for (int i = 0, j = n - 1; i <= j;) {
            // find the largest number that meets the sum condition
            if (nums[i] + nums[j] > target)
                j--;
            else {
                // add all possible combinations in [i + 1, j], and then in theory we will add
                // nums[i] to all those combinations to get the correct min & max
                ans = (ans + powerOfTwo[j - i]) % mod;
                i++;
            }
        }
        return ans;
    }
}
```