#2915

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Length of the Longest Subsequence That Sums to Target

Find the length of the longest subsequence in an array that sums to a target value, using dynamic programming.

Problem Statement

You are given a 0-indexed array of integers nums, and an integer target. Your task is to return the length of the longest subsequence of nums that sums up to the target value.

A subsequence is a sequence derived from another array by deleting some or no elements, without changing the order of the remaining elements. If no subsequence can achieve the target sum, return -1.

Examples

Example 1

Input: nums = [1,2,3,4,5], target = 9

Output: 3

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

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

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

Solution Approach

Dynamic Programming State Transition

The core idea is to maintain a state array where each entry represents the longest subsequence sum up to a certain value. Start by iterating through the elements and updating possible sums using dynamic programming to track the longest subsequence length for each sum.

Greedy + DP Optimization

You can optimize the dynamic programming solution by using a greedy approach to add elements to the subsequence. Focus on adding numbers that bring you closer to the target while maintaining the longest subsequence.

Backtracking for Valid Solutions

In case a straightforward DP approach doesn’t directly lead to a valid subsequence, backtracking can be employed. This ensures you explore all possible subsequences for achieving the target sum.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the specific implementation, with dynamic programming offering an optimized solution in O(n * target) time and space, where n is the length of the input array and target is the target sum.

What Interviewers Usually Probe

Can the candidate explain the dynamic programming approach effectively?
Do they recognize that backtracking is only used if DP doesn't yield the solution?
Are they able to optimize the space complexity by using a greedy approach or a reduced state transition table?

Common Pitfalls or Variants

Common pitfalls

Failing to correctly handle edge cases where no subsequence exists that sums to the target.
Not understanding the necessity of updating the dynamic programming state in a way that ensures the subsequence is as long as possible.
Using brute-force methods instead of dynamic programming, leading to inefficient solutions.

Follow-up variants

What if the target value is zero? The solution would need to handle the edge case where an empty subsequence is a valid answer.
What if the input array is sorted? Could that lead to potential optimizations in the DP approach?
How does this approach change if elements in nums can be negative?

FAQ

What is the main approach for solving the Length of the Longest Subsequence That Sums to Target problem?

The main approach involves using dynamic programming to track possible subsequence sums and their lengths. A state transition method is applied to update the longest subsequence for each sum.

How do dynamic programming and greedy approaches optimize this problem?

Dynamic programming helps in maintaining a table of subsequence sums, while the greedy approach ensures the longest subsequence is found by adding optimal elements. Both can be combined for more efficient solutions.

Why does the Length of the Longest Subsequence That Sums to Target problem use state transition?

State transition allows for tracking how subsequences evolve as you process each element, helping to efficiently find the longest subsequence that sums to the target value.

What happens if there is no valid subsequence in this problem?

If no subsequence sums to the target, the solution should return -1, indicating that it is not possible to achieve the target sum.

How can GhostInterview assist with dynamic programming problems like this one?

GhostInterview guides you through the process of building a dynamic programming solution, helping you understand state transitions and identify key optimizations for more efficient solutions.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ as the length of the longest subsequence that selects several numbers from the first $i$ numbers and the sum of these numbers is exactly $j$. Initially, $f[0][0]=0$, and all other positions are $-\infty$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        n = len(nums)
        f = [[-inf] * (target + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(nums, 1):
            for j in range(target + 1):
                f[i][j] = f[i - 1][j]
                if j >= x:
                    f[i][j] = max(f[i][j], f[i - 1][j - x] + 1)
        return -1 if f[n][target] <= 0 else f[n][target]

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        n = len(nums)
        f = [[-inf] * (target + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(nums, 1):
            for j in range(target + 1):
                f[i][j] = f[i - 1][j]
                if j >= x:
                    f[i][j] = max(f[i][j], f[i - 1][j - x] + 1)
        return -1 if f[n][target] <= 0 else f[n][target]

Continue Practicing

#2916 subarrays distinct element sum of squares ii #2919 minimum increment operations to make array beautiful #2920 maximum points after collecting coins from all nodes