We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Length of the Longest Subsequence That Sums to Target

Number: 3106

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Intuit

Problem Description

Given an array of positive integers nums and an integer target, return the length of the longest subsequence of nums whose elements sum exactly to target. If no such subsequence exists, return -1.

Key Insights

  • The problem is a variant of the classic subset sum problem.
  • Since all numbers are positive, dynamic programming can be effectively used.
  • Instead of tracking whether a sum is achievable, we need to track the maximum length used to form that sum.
  • Iterate through the nums and update a dp table for sums from target down to the current number to ensure each element is used at most once.

Space and Time Complexity

Time Complexity: O(n * target) where n is the length of nums. Space Complexity: O(target) for the dp array.

Solution

We use dynamic programming with a one-dimensional dp array where dp[j] represents the maximum length of a subsequence that sums to j. Initialize dp[0] to 0 (zero elements yield sum 0) and others to a very small number (or a flag value to indicate not achievable). Then, for each number in the nums array, update the dp table in reverse order (from target down to the current number) to avoid reusing the same element. After processing, if dp[target] remains at initialization value, no valid subsequence exists and return -1; otherwise, dp[target] gives the length of the longest subsequence.

Code Solutions

# Python solution for Length of the Longest Subsequence That Sums to Target

def longestSubsequence(nums, target):
    # Initialize dp array with -infinity (use a very small number)
    dp = [-float('inf')] * (target + 1)
    dp[0] = 0  # zero elements form sum of 0
    
    for num in nums:
        # Traverse backwards to avoid using the same element more than once
        for j in range(target, num - 1, -1):
            if dp[j - num] != -float('inf'):
                dp[j] = max(dp[j], dp[j - num] + 1)
                
    # If dp[target] is still -infinity, no valid subsequence exists.
    return dp[target] if dp[target] != -float('inf') else -1

# Example usage:
print(longestSubsequence([1,2,3,4,5], 9))  # Output: 3
print(longestSubsequence([4,1,3,2,1,5], 7))  # Output: 4
print(longestSubsequence([1,1,5,4,5], 3))  # Output: -1
← Back to All Questions