2915. Length of the Longest Subsequence That Sums to Target LeetCode Solution
In this guide, you will get 2915. Length of the Longest Subsequence That Sums to Target LeetCode Solution with the best time and space complexity. The solution to Length of the Longest Subsequence That Sums to Target problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
2915. Length of the Longest Subsequence That Sums to Target LeetCode Solution in C++
class Solution {
public:
int lengthOfLongestSubsequence(vector<int>& nums, int target) {
const int n = nums.size();
// dp[i][j] := the maximum length of any subsequence of the first i numbers
// that sum to j
vector<vector<int>> dp(n + 1, vector<int>(target + 1, -1));
for (int i = 0; i <= n; ++i)
dp[i][0] = 0;
for (int i = 1; i <= n; ++i) {
const int num = nums[i - 1];
for (int j = 1; j <= target; ++j)
// 1. Skip `num`.
if (j < num || dp[i - 1][j - num] == -1)
dp[i][j] = dp[i - 1][j];
// 2. Skip `num` or pick `num`.
else
dp[i][j] = max(dp[i - 1][j], 1 + dp[i - 1][j - num]);
}
return dp[n][target];
}
}; /* code provided by PROGIEZ */
2915. Length of the Longest Subsequence That Sums to Target LeetCode Solution in Java
class Solution {
public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
final int n = nums.size();
// dp[i][j] := the maximum length of any subsequence of the first i numbers
// that sum to j
int[][] dp = new int[n + 1][target + 1];
Arrays.stream(dp).forEach(A -> Arrays.fill(A, -1));
for (int i = 0; i <= n; ++i)
dp[i][0] = 0;
for (int i = 1; i <= n; ++i) {
final int num = nums.get(i - 1);
for (int j = 1; j <= target; ++j) {
// 1. Skip `num`.
if (j < num || dp[i - 1][j - num] == -1)
dp[i][j] = dp[i - 1][j];
// 2. Skip `num` or pick `num`.
else
dp[i][j] = Math.max(dp[i - 1][j], 1 + dp[i - 1][j - num]);
}
}
return dp[n][target];
}
} // code provided by PROGIEZ
2915. Length of the Longest Subsequence That Sums to Target LeetCode Solution in Python
class Solution:
def lengthOfLongestSubsequence(self, nums: list[int], target: int) -> int:
n = len(nums)
# dp[i][j] := the maximum length of any subsequence of the first i numbers
# that sum to j
dp = [[-1] * (target + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = 0
for i in range(1, n + 1):
num = nums[i - 1]
for j in range(1, target + 1):
# 1. Skip `num`.
if j < num or dp[i - 1][j - num] == -1:
dp[i][j] = dp[i - 1][j]
# 2. Skip `num` or pick `num`.
else:
dp[i][j] = max(dp[i - 1][j], 1 + dp[i - 1][j - num])
return dp[n][target] # code by PROGIEZ
