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.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Length of the Longest Subsequence That Sums to Target solution in C++
  4. Length of the Longest Subsequence That Sums to Target solution in Java
  5. Length of the Longest Subsequence That Sums to Target solution in Python
  6. Additional Resources
2915. Length of the Longest Subsequence That Sums to Target LeetCode Solution image

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.

See also  17. Letter Combinations of a Phone Number LeetCode Solution

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

Complexity Analysis

  • Time Complexity: O(n \cdot \texttt{target})
  • Space Complexity: O(n \cdot \texttt{target})

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

Additional Resources

See also  1625. Lexicographically Smallest String After Applying Operations LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.