Algorithms
Medium
2915
3106
Length of the Longest Subsequence That Sums to Target
length-of-the-longest-subsequence-that-sums-to-target
"""
You are given a 0-indexed array of integers nums, and an integer target.

Return the length of the longest subsequence of nums that sums up to target. If no such subsequence exists, return -1.

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.

Example 1:

Input: nums = [1,2,3,4,5], target = 9
Output: 3
Explanation: 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.

Example 2:

Input: nums = [4,1,3,2,1,5], target = 7
Output: 4
Explanation: 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.

Example 3:

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


Constraints:

 * 1 <= nums.length <= 1000
 * 1 <= nums[i] <= 1000
 * 1 <= target <= 1000
"""
class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        
You are given a 0-indexed array of integers nums, and an integer target.

Return the length of the longest subsequence of nums that sums up to target. If no such subsequence exists, return -1.

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.

Example 1:

Input: nums = [1,2,3,4,5], target = 9
Output: 3
Explanation: 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.

Example 2:

Input: nums = [4,1,3,2,1,5], target = 7
Output: 4
Explanation: 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.

Example 3:

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


Constraints:

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


Please complete the code below to solve above prblem:
```python
class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [1,2,3,4,5], "target": 9 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 3

test_input = { "nums": [4,1,3,2,1,5], "target": 7 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 4

test_input = { "nums": [1,1,5,4,5], "target": 3 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == -1

test_input = { "nums": [1000], "target": 12 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == -1

test_input = { "nums": [1000], "target": 1000 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 1

test_input = { "nums": [1,2], "target": 10 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == -1

test_input = { "nums": [1,1000], "target": 5 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == -1

test_input = { "nums": [2,3], "target": 3 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 1

test_input = { "nums": [2,3], "target": 5 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 2

test_input = { "nums": [2,3,5], "target": 5 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 2

test_input = { "nums": [1,3,3,7], "target": 1000 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == -1

test_input = { "nums": [1,3,3,7], "target": 2 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == -1

test_input = { "nums": [1,3,3,8], "target": 7 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 3

test_input = { "nums": [1,1,2,1], "target": 2 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 2

test_input = { "nums": [1,1,1,1], "target": 5 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == -1

test_input = { "nums": [1,1,1,2], "target": 3 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 3

test_input = { "nums": [9,12,8,4,11,13,15,7,5], "target": 84 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [11,5,9,11,12,13,12,5,1,8], "target": 87 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [9,11,11,15,4,14,3,2,13,7], "target": 89 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [11,13,6,13,10], "target": 53 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5

test_input = { "nums": [10,3,5,11,6,12], "target": 47 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [13,3,6,6,6,15,4], "target": 53 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [1,6,15,6,14,13,14], "target": 69 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [10,7,8,14,15], "target": 54 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5

test_input = { "nums": [14,15,8,10,8,7], "target": 62 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [7,9,14,14,9,14,5,12,10], "target": 94 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [1,10,6,14,5,13,3,7,10,10], "target": 79 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [5,2,8,6,7,12,13,4,1], "target": 58 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [12,8,2,4,1], "target": 27 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5

test_input = { "nums": [10,14,11,13,2,11], "target": 61 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [10,2,13,5,7,15], "target": 52 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [3,1,10,1,10,1,2,9,5,13], "target": 55 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [5,13,2,13,9,4,5,7], "target": 58 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 8

test_input = { "nums": [1,15,5,12,13,10,14,8], "target": 78 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 8

test_input = { "nums": [7,4,14,10,13], "target": 48 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5

test_input = { "nums": [6,14,14,6,2,9,1,4,10], "target": 66 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [14,15,7,5,7,10,6,14,10,11], "target": 99 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [15,13,8,8,6], "target": 50 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5

test_input = { "nums": [2,6,8,9,13,3], "target": 41 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [13,15,9,3,8,1,9,2,15,5], "target": 80 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [5,13,9,11,6,1], "target": 45 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [7,10,15,7,14,2], "target": 55 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [12,14,13,13,13], "target": 65 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5

test_input = { "nums": [12,8,7,9,3,10,3,8,2], "target": 62 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [11,1,14,13,14,4,14,11], "target": 82 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 8

test_input = { "nums": [5,9,11,2,5,2,7,11,5,3], "target": 60 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [5,15,3,13,14,15,10], "target": 75 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [10,8,2,2,9], "target": 31 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5

test_input = { "nums": [7,15,4,3,9,15,12,1,12], "target": 78 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [3,1,12,15,5,10], "target": 46 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [5,3,12,7,5,2,12,10,12,5], "target": 73 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [6,10,3,1,7,11,9,8,13,12], "target": 80 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [11,3,4,11,9], "target": 38 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5

test_input = { "nums": [15,12,12,13,6,6,4,1], "target": 69 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 8

test_input = { "nums": [9,2,10,7,10,11,14,11,8], "target": 82 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [4,4,3,9,6,8,4,7,7], "target": 52 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [10,14,4,15,9,5], "target": 57 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [4,13,2,3,13,11,8,6], "target": 60 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 8

test_input = { "nums": [1,7,8,14,15,9,8,10,13,7], "target": 92 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [7,7,6,14,7,4], "target": 45 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [9,10,9,7,14,3,6,4,6], "target": 68 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [15,13,14,5,7,13,11,14], "target": 92 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 8

test_input = { "nums": [1,1,10,12,5,6,15,6,8], "target": 64 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [14,13,13,11,14,13,8], "target": 86 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [3,14,4,2,10,3,7], "target": 43 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [6,1,3,11,9,2,10,6,12], "target": 60 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [6,2,5,4,12], "target": 29 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5

test_input = { "nums": [7,11,15,1,9,9,11], "target": 63 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [7,12,10,15,6,15,14,2], "target": 81 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 8

test_input = { "nums": [12,3,10,12,13,3,4,7,15], "target": 79 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [14,6,11,2,10,1,12,9,2], "target": 67 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [5,8,12,6,15,13,11], "target": 70 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [11,6,1,6,2,6,15], "target": 47 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [12,7,15,10,5,4,7,12,12], "target": 84 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [11,4,4,9,10,7,12], "target": 57 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [4,12,15,6,15,1,4,4,2], "target": 63 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [3,13,4,15,1], "target": 36 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5

test_input = { "nums": [14,3,7,14,7,7,1,6], "target": 59 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 8

test_input = { "nums": [15,13,1,14,6,8], "target": 57 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [14,2,3,10,15], "target": 44 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5

test_input = { "nums": [5,5,3,7,12,10,11], "target": 53 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [3,7,3,5,3,14,8], "target": 43 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [5,7,9,14,9,14,4,1,4], "target": 67 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [12,7,8,6,3,9,7,3,4,4], "target": 63 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [9,12,1,4,9,6,15,9,7], "target": 72 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [9,13,12,10,4,9,9,4,4,13], "target": 87 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [13,5,6,8,2,13,1,5,6], "target": 59 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [7,9,8,9,9,3,5], "target": 50 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [15,1,14,8,2,1,10,15,15], "target": 81 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [13,14,1,9,12,2], "target": 51 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [13,12,12,13,8,11,3,14,13], "target": 99 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [2,2,1,12,10,7,11,5,5], "target": 55 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [13,10,3,4,10,3], "target": 43 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 6

test_input = { "nums": [8,9,1,5,8,7,6,8], "target": 52 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 8

test_input = { "nums": [10,1,4,10,9,13,14], "target": 61 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 7

test_input = { "nums": [3,14,11,4,7,9,7,6,8,11], "target": 80 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 10

test_input = { "nums": [4,11,6,6,14,12,2,9,1], "target": 65 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 9

test_input = { "nums": [9,2,15,12,15,6,4,12], "target": 75 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 8

test_input = { "nums": [4,3,5,3,2], "target": 17 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5

test_input = { "nums": [4,3,13,6,9], "target": 35 }
assert my_solution.lengthOfLongestSubsequence(**test_input) == 5