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

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        l = len(nums)
        if l == 1:
            if nums[0] == target:
                return 1
            else:
                return -1

        nums.sort()
        prefixSum = [0] * l
        prefixSum[0] = nums[0]
        for i in range(1, l):
            prefixSum[i] = nums[i] + prefixSum[i-1]

        totalSum = sum(nums)
        if totalSum < target:
            return -1

        dp = [[-1 for i in range(target+1)] for j in range(l+1)]

        for i in range(l+1):
            dp[i][0] = 0
        
        for j in range(1, target+1):
            dp[0][j] = -1
        

        for i in range(1, l+1):
            for j in range(1, target+1):
                if prefixSum[i-1] < j:
                    continue

                if dp[i-1][j] >= 0:
                    dp[i][j] = max(dp[i-1][j], dp[i][j])

                if j >= nums[i-1] and dp[i-1][j-nums[i-1]] >= 0:
                    dp[i][j] = max(dp[i-1][j-nums[i-1]]+1, dp[i][j])
        
        return dp[l][target]


## in-efficient
# class Solution:
#     def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
#         l = len(nums)
#         if l == 1:
#             if nums[0] == target:
#                 return 1
#             else:
#                 return -1

#         nums.sort()
#         prefixSum = [0] * l
#         prefixSum[0] = nums[0]
#         for i in range(1, l):
#             prefixSum[i] = nums[i] + prefixSum[i-1]

#         totalSum = sum(nums)
#         if totalSum < target:
#             return -1

#         dp = [[(False, -1) for i in range(totalSum+1)] for j in range(l+1)]

#         for i in range(l+1):
#             dp[i][0] = (True, 0)
        
#         for j in range(1, totalSum+1):
#             dp[0][j] = (False, -1)
        

#         for i in range(1, l+1):
#             for j in range(1, target+1):
#                 if prefixSum[i-1] < j:
#                     continue

#                 prev, prevLen = dp[i-1][j]
#                 if prev:
#                     maxL = max(prevLen, dp[i][j][1])
#                     dp[i][j] = (True, maxL)

#                 if j >= nums[i-1] and dp[i-1][j-nums[i-1]][0]:
#                     prev, prevLen = dp[i-1][j-nums[i-1]]
#                     maxL = max(prevLen+1, dp[i][j][1])
#                     dp[i][j] = (True, maxL)
        
#         return dp[l][target][1]

## in-efficient
# class Solution:
#     def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
#         l = len(nums)
#         if l == 1:
#             if nums[0] == target:
#                 return 1
#             else:
#                 return -1
    
#         self.dp = {}
#         self.nums = nums

#         self.ans = 0
#         self.lengthOfLongestSubsequenceUtil(l-1, 0, target, 0)
        
#         if self.ans == 0:
#             return -1
#         return self.ans
    
#     def lengthOfLongestSubsequenceUtil(self, pos, length, tgt, accum):
#         if pos < 0 and accum == tgt:
#             self.ans = max(self.ans, length)
        
#         if pos < 0:
#             return

#         if (pos, length, accum) in self.dp:
#             return
        
#         # include
#         self.lengthOfLongestSubsequenceUtil(pos-1, length+1, tgt, accum+self.nums[pos])

#         # exclude
#         self.lengthOfLongestSubsequenceUtil(pos-1, length, tgt, accum)
    
#         self.dp[(pos, length, accum)] = True
#         return

5410