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 10^9 + 7.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3
4

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:

1
2
3
4

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).

Solution

Method 1 - Recursion + Backtracking

graph TD;
	A("[3, 3, 6, 8], tgt = 10") --> B(3) & C("[]")
	B --> D("[3,3]") & E("[3]")
	C --> F("[3]") & G("[]")

Time complexity - O(2^n)

Method 2 - Using Two Sum

  1. This problem is a variant of the Two Sum.
  2. In this scenario, the order of numbers in a subsequence is irrelevant; only the maximum and minimum values of the subsequence matter. Therefore, a subsequence from index i to j in the original array is equivalent to an array with the same elements and the same minimum and maximum values. For example, consider nums = [3, 7, 6, 5] and target = 10. Here, the subsequence [3, 7, 6] is equivalent to the subsequence [3, 6, 7] of the sorted array [3, 5, 6, 7]. Thus, the result for nums is the same as the result for sorted(nums).
  3. For each index i in sorted_nums, identify the maximum index j such that sorted_nums[i] + sorted_nums[j] <= target and j >= i.
  4. From i+1 to j, each element can either be included or excluded.
  5. Therefore, res += 2^(j-i).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

 public int numSubseq(int[] nums, int target) {
     Arrays.sort(nums);  // Sort the array first
     int res = 0, n = nums.length, l = 0, r = n - 1;
     int mod = (int) 1e9 + 7;
     int[] pows = new int[n];
     pows[0] = 1;
     
     // Precompute powers of 2 modulo mod
     for (int i = 1; i < n; ++i) {
         pows[i] = pows[i - 1] * 2 % mod;
     }
 
     // Use two pointers to find subsequences
     while (l <= r) {
         if (nums[l] + nums[r] > target) {
             r--;
         } else {
             res = (res + pows[r - l++]) % mod;
         }
     }
     
     return res;
 }

Complexity

  • ⏰ Time complexity: O(n log n), for sorting the array.
    • O(n) as each element is processed at most twice.
  • 🧺 Space complexity: O(n)
    • Auxiliary Space: O(n) for storing the precomputed powers of 2 in the array pows.