Recursive DP | Python | Memoization | Manual Cache Flushing
Intuition\nA simple DP solution. We just have to either take or not take.\n\n# Approach\n- We have recursively either including an index or not. \n- If at the e
# Intuition\nA simple DP solution. We just have to either take or not take.\n\n# Approach\n- We have recursively either including an index or not. \n- If at the end the chosen sequence is equal to the target, we would return `0` as a base case, otherwise we would return `-inf`\n\nI have sorted the nums, so that while implementing the recursive solution, we can just exit the recursion if the target left to achieve is smaller than the current element.\n\nFor memoisation I would not recomment using the decorators `@cache` or `@lru_cache` because then it would lead to MLE as you wouldn\'t be able to flush the cached memory. (If you know how to flush cached memory of these decorators, please do comment)\n\n# Rant (...sorry)\nLeetCode really need to work on their garbage collection as it rejected my code two times (once MLE and once TLE), just because they didn\'t flush out all the cached memory left from the operations on the previous testcases.\n\nI had to manually flush the memory I was using to memoise using `memo.clear()` to get my answer submitted. It pushed my ranking from 150 to 1500, ten times increase!\n\nHoping leetcode improves their garbage collection soon.\n\n# Complexity\n- Time complexity: $$O(n * total)$$ (max: $$O(10^6)$$)\n\n- Space complexity: $$O(n * total)$$ (max: $$O(10^6)$$)\n\n# Code\n```python\ndef lengthOfLongestSubsequence(nums: List[int], target: int) -> int:\n    nums.sort()\n    n = len(nums)\n    \n    memo = {}\n    def dp(index: int, total: int) -> int:\n        if (index, total) in memo:\n            return memo[(index, total)]\n        if total == 0:\n            return 0\n        if index == n or total < nums[index]:\n            return -float("inf")\n        res = max(1 + dp(index + 1, total - nums[index]), dp(index + 1, total))\n        memo[(index, total)] = res\n        return res\n        \n        \n    res = dp(0, target)\n    memo.clear() # absence of this would result in a MLE\n    return res if res != -float("inf") else -1\n```\n\n# Thanks for your audience\nPlease upvote if you liked
['Dynamic Programming', 'Recursion', 'Memoization', 'Python3']