Number of Subsequences That Satisfy the Given Sum Condition
- 1 min read
- LC-Medium
3 years ago
Solution
- Naive solution is using recursive DFS- but this solution TLEs
| Time | Space | Explanation |
|---|---|---|
O() | O() |
Naive Solution (Recursive DFS, TLEs)
def numSubseq(self, nums: List[int], target: int) -> int:
ans = 0
def dfs(i, cur_min, cur_max):
nonlocal ans
if i == len(nums):
if cur_min != math.inf and cur_max != -math.inf and (cur_min + cur_max) <= target:
ans += 1
return
dfs(i + 1, cur_min, cur_max)
new_min = nums[i] if cur_min == math.inf else min(cur_min, nums[i])
new_max = nums[i] if cur_max == math.inf else max(cur_max, nums[i])
dfs(i + 1, new_min, new_max)
dfs(0, math.inf, -math.inf)
return ans % (10 ** 9 + 7)