Number of Subsequences That Satisfy the Given Sum Condition

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.

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

def count_subsequences(nums, target):
    nums.sort()
    n = len(nums)
    left, right = 0, n - 1
    count = 0
    mod = 10**9 + 7
    power = [1] * (n + 1)
    for i in range(1, n + 1):
        power[i] = (power[i - 1] * 2) % mod

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

    return count

# Example 1
nums1 = [3, 5, 6, 7]
target1 = 9
print(f"Example 1: {count_subsequences(nums1, target1)}")

# Example 2
nums2 = [3, 3, 6, 8]
target2 = 10
print(f"Example 2: {count_subsequences(nums2, target2)}")

# Example 3
nums3 = [2, 3, 3, 4, 6, 7]
target3 = 12
print(f"Example 3: {count_subsequences(nums3, target3)}")

Explanation:

1. Sort the Array: The array nums is sorted in ascending order. This makes it easier to find the minimum and maximum elements that satisfy the condition.
2. Two Pointers: Two pointers, left and right, are initialized to the start and end of the array, respectively.
3. Iterate and Count:
   • If nums[left] + nums[right] <= target, then any subsequence with nums[left] as the minimum and any combination of elements between left + 1 and right will satisfy the condition. The number of such subsequences is 2**(right - left). This is because each element between left + 1 and right can either be included or excluded from the subsequence.
   • If nums[left] + nums[right] > target, it means that nums[right] is too large. Therefore, we decrement right to find a smaller maximum value.
4. Power Calculation: The power array is precomputed to store the powers of 2 modulo 10**9 + 7. This avoids repeatedly calculating the power of 2 in the loop, which improves efficiency.
5. Modulo Arithmetic: All calculations are done modulo 10**9 + 7 to prevent overflow.

Time and Space Complexity

Time Complexity:

• Sorting the array takes O(n log n) time.
• The two-pointer approach takes O(n) time.
• Therefore, the overall time complexity is O(n log n).

Space Complexity:

• The power array takes O(n) space.
• Therefore, the overall space complexity is O(n).

Edge Cases

1. Empty Array: If the input array is empty, the function should return 0 because there are no non-empty subsequences.
2. Single Element Array: If the input array contains only one element, the function should return 1 if the element is less than or equal to target, and 0 otherwise.
3. Target Smaller Than Minimum Element: If the target is smaller than twice the minimum element in the array, the function should return 0 because no subsequence can satisfy the condition.
4. Duplicate Elements: The code handles duplicate elements correctly because it considers all possible subsequences. The powers of 2 calculation accounts for the combinations of including or excluding elements between the left and right pointers.