Number Of Subsequences That Satisfy The Given Sum Condition

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• Sort the array
• Then, notice that your left and right pointers when set to 0 and n - 1, point to the min and max.
• Those are the only values that ultimately matter. Then, you may notice:
  • Whenever you have the min and max, when added up, becoming > target, you may simply move the right pointer one to the left, thereby making the array smaller.
  • But if the cur_sum $\le$ target, this means that exactly $2^{\text{right - left}}$ subsequence combinations exist which include that min.
  • Why?
    • ex) [3, 5, 6, 7], when left = 0, right = 2, contains [3, 6], [3, 5], [3, 3], and [5, 6] as combinations.
      • In other words, the two numbers that are less than the max form combinations with each other.
      • This combination doesn’t include [5, 5], since that is not guaranteed to be $\le$ target, and so we disinclude that.

Complexity

Runtime

$O(NlogN)$ due to sorting

Space

$O(N)$ due to TimSort

Code

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        MOD = 10**9 + 7
 
        @cache
        def count_subsequences(left, right):
            if left > right:
                return 0
            
            if nums[left] + nums[right] > target:
                return count_subsequences(left, right - 1)
            
            # Count all valid subsets that include nums[left]
            return (pow(2, right - left, MOD) + count_subsequences(left + 1, right)) % MOD
        
        return count_subsequences(0, len(nums) - 1)

• Far easier to solve iteratively

Notes

Cards

START Basic Front: Number Of Subsequences That Satisfy The Given Sum Condition Back:

END

---

References

• Number Of Subsequences That Satisfy The Given Sum Condition