<p>You are given a <strong>0-indexed</strong> array of integers <code>nums</code>, and an integer <code>target</code>.</p>

<p>Return <em>the <strong>length of the longest subsequence</strong> of</em> <code>nums</code> <em>that sums up to</em> <code>target</code>. <em>If no such subsequence exists, return</em> <code>-1</code>.</p>

<p>A <strong>subsequence</strong> is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5], target = 9
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are 3 subsequences with a sum equal to 9: [4,5], [1,3,5], and [2,3,4]. The longest subsequences are [1,3,5], and [2,3,4]. Hence, the answer is 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,1,3,2,1,5], target = 7
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 5 subsequences with a sum equal to 7: [4,3], [4,1,2], [4,2,1], [1,1,5], and [1,3,2,1]. The longest subsequence is [1,3,2,1]. Hence, the answer is 4.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,5,4,5], target = 3
<strong>Output:</strong> -1
<strong>Explanation:</strong> It can be shown that nums has no subsequence that sums up to 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= target &lt;= 1000</code></li>
</ul>

"""
You are given a 0-indexed array of integers nums, and an integer target.
- nums and target is postive, N+
- len(nums): small
- target: small
- nums[i]: small
- taking a number always decreases amount

Return the length of the longest subsequence of nums that sums up to target. If no such subsequence exists, return -1.
- "Picking" an element that decreases our target to the goal is optimal, thus we wish to *maximise* the picking whilst still
reaching the target goal, maximise(maximal index count, reaching target)
- Only one picking of an element is allowed, no reuse, thus we take or skip then move on, no re-using elements
- CAN'T reuse elemnts, must always increment to the next index regardless of decision

- Decisions: Pick or Skip
    - Pick: Adds one to length, decreases targer we are searching for
        - Path isnt viable when the target is reduced below zero, < 0
        - Path is viable when length is zero
    - Skip: Index is increased, target remains


A subsequence is an array that can be derived from another array by deleting some or no elements 
without changing the order of the remaining elements.
Ordering: Left -> Right or Right -> Left, just stick with it

01 Knapsack, take or give, the maximal length obtained from either avenue
Sample case:
- nums = [1,2,3,4,5], target = 9, left -> right ordering
Take the 1st num in nums
    - Find remaining amount, 9 - 1 = 8 target, move on to 2nd num (2)
    - Take target 8 - 2 = 6 target (take and skip this also), skip 2nd num to 3rd num (3) 8 - 3 = 5 target...
    - ensure amount suffices -> when target is 0, then amount suffices

Skip to 2nd num -> increment index counter
    - target remains as 9
    - ensure base case is reached with index, checking if target == 0 is our base case

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
1 <= target <= 1000

(skip or take)
Reccurence Relation:
        === dp(index, currentTarget) ===
       { 1 + dp(index + 1, currentTarget - cost)  # TAKE - Cost of taking + next exploration
max -> { dp(index + 1, currentTarget) # SKIP - next exploration
       { currentTarget == 0 ? then 1, else return -1 (Navigated path is a "dead end" does not provide) <- Maintain invariance



"""

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        self.longest, self.n = 0, len(nums)
        max_allowed = 1001
        dp = [[-max_allowed] * max_allowed for i in range(self.n)]
        
        # if sum(nums) < target:
        #     return -1
        # if min(nums) > target:
        #     return -1

        # @cache
        def longestLengthSubsequnceToSumTarget(i: int, curTarget: int):
            if curTarget == 0: # Base case, for taking
                return 0
            
            if curTarget < 0 or i >= self.n: # Base case, for skipping or taking, well-defined indexing and target
                return -1001

            if dp[i][curTarget] != -1001:
                return dp[i][curTarget]

            # ACTIONS: Take or Skip
            
            # Take
            take = 1 + longestLengthSubsequnceToSumTarget(i + 1, curTarget - nums[i])

            # Skip
            skip = longestLengthSubsequnceToSumTarget(i + 1, curTarget)

            dp[i][curTarget] = max(take, skip)
            return dp[i][curTarget]

    
        ans = longestLengthSubsequnceToSumTarget(0, target)
        print(ans)
        return -1 if ans <= 0 else ans
103972