LeetCode 2915 - Length of the Longest Subsequence That Sums to Target
The problem gives us an array nums and an integer target. We must find a subsequence whose elements add up exactly to target, while maximizing the number of elements included in that subsequence.
Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming
Solution
LeetCode 2915 - Length of the Longest Subsequence That Sums to Target
Problem Understanding
The problem gives us an array nums and an integer target. We must find a subsequence whose elements add up exactly to target, while maximizing the number of elements included in that subsequence.
A subsequence is formed by deleting zero or more elements from the original array without changing the relative order of the remaining elements. Since we are only interested in the sum of the chosen elements and not their positions beyond order preservation, the task becomes finding the maximum possible subsequence length among all subsequences whose sum equals target.
The output should be the length of the longest valid subsequence. If no subsequence can produce the target sum, we return -1.
The constraints are important:
1 <= nums.length <= 10001 <= nums[i] <= 10001 <= target <= 1000
The array can contain up to 1000 elements, which immediately makes exhaustive subsequence enumeration impossible because there are 2^n possible subsequences.
A key observation is that although n can be as large as 1000, the target value is also bounded by 1000. This suggests a dynamic programming solution where states are based on achievable sums rather than on subsets.
Some important edge cases include:
- No subsequence sums to the target, in which case we return
-1. - A single element equals the target.
- Multiple subsequences achieve the target, but with different lengths.
- All elements are larger than the target.
- Many duplicate values exist.
- The longest valid subsequence may not use the largest values.
Because all numbers are positive, once a sum exceeds the target, it can never become useful again. This property helps keep the dynamic programming state small.
Approaches
Brute Force
The most straightforward approach is to generate every possible subsequence.
For each subsequence, we compute its sum and length. If the sum equals target, we compare its length with the best answer found so far.
This approach is correct because it examines every possible subsequence and therefore cannot miss the optimal one.
Unfortunately, an array of length n has 2^n subsequences. With n = 1000, this is astronomically large and completely infeasible.
Dynamic Programming
The key insight is that the target is at most 1000.
Instead of tracking which elements are chosen, we track achievable sums. For every possible sum s, we store the maximum subsequence length that can produce that sum.
Let:
dp[s] = maximum length of a subsequence whose sum is s
Initially:
dp[0] = 0, because an empty subsequence has sum 0 and length 0.- All other states are impossible.
When processing a number num, we update sums in reverse order, exactly like the classic 0/1 knapsack pattern.
If a sum s - num is achievable, then including num creates sum s with length:
dp[s - num] + 1
We keep the maximum length for every sum.
After processing all elements, dp[target] contains the length of the longest subsequence that sums to the target.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | Enumerates all subsequences |
| Optimal DP | O(n × target) | O(target) | Knapsack-style DP storing maximum lengths |
Algorithm Walkthrough
- Create a DP array of size
target + 1. - Initialize every state as impossible using
-1. - Set
dp[0] = 0because sum 0 can always be formed with an empty subsequence. - Process each number
numinnums. - For each number, iterate sums from
targetdown tonum. - For every sum
s, check whetherdp[s - num]is achievable. - If it is achievable, then selecting the current number creates a candidate subsequence with:
candidate_length = dp[s - num] + 1
8. Update:
dp[s] = max(dp[s], candidate_length)
9. Reverse iteration is critical because each element may only be used once. Updating from high sums to low sums prevents reusing the same element multiple times during a single iteration.
10. After all numbers are processed, return dp[target].
11. If dp[target] remains -1, no valid subsequence exists, so return -1.
Why it works
The invariant is that after processing the first i elements, dp[s] stores the maximum subsequence length obtainable with sum s using only those processed elements.
When a new element is considered, every existing achievable sum can either ignore the element or include it. The transition examines both possibilities and keeps the better length. Reverse iteration guarantees each array element contributes at most once. Therefore, after all elements are processed, dp[target] represents the longest subsequence whose sum equals the target.
Python Solution
from typing import List
class Solution:
def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
dp = [-1] * (target + 1)
dp[0] = 0
for num in nums:
for curr_sum in range(target, num - 1, -1):
if dp[curr_sum - num] != -1:
dp[curr_sum] = max(
dp[curr_sum],
dp[curr_sum - num] + 1
)
return dp[target]
The implementation uses a one-dimensional DP array where each index represents a possible sum.
The value stored at dp[s] is the maximum subsequence length that achieves sum s. Impossible sums are represented by -1.
The initialization dp[0] = 0 represents the empty subsequence.
For each number, the algorithm scans sums backward. Whenever a previous sum is achievable, the current number can extend that subsequence by one element. The maximum length is preserved with max().
After all numbers are processed, the answer is already stored in dp[target].
Go Solution
func lengthOfLongestSubsequence(nums []int, target int) int {
dp := make([]int, target+1)
for i := 1; i <= target; i++ {
dp[i] = -1
}
dp[0] = 0
for _, num := range nums {
for sum := target; sum >= num; sum-- {
if dp[sum-num] != -1 {
candidate := dp[sum-num] + 1
if candidate > dp[sum] {
dp[sum] = candidate
}
}
}
}
return dp[target]
}
The Go implementation follows exactly the same dynamic programming logic.
Since Go slices are initialized with zeros, we explicitly set all states except dp[0] to -1 to represent impossible sums. Integer overflow is not a concern because the maximum subsequence length is at most 1000.
Worked Examples
Example 1
Input
nums = [1,2,3,4,5]
target = 9
Initial state:
| Sum | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| dp | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
After processing 1:
| Sum | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| dp | 0 | 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
After processing 2:
| Sum | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| dp | 0 | 1 | 1 | 2 | -1 | -1 | -1 | -1 | -1 | -1 |
After processing 3:
| Sum | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| dp | 0 | 1 | 1 | 2 | 2 | 2 | 3 | -1 | -1 | -1 |
After processing 4:
| Sum | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| dp | 0 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 3 |
After processing 5:
| Sum | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| dp | 0 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 3 |
Final answer:
dp[9] = 3
Example 2
Input
nums = [4,1,3,2,1,5]
target = 7
Key transitions:
| Element | Important New States |
|---|---|
| 4 | dp[4] = 1 |
| 1 | dp[1] = 1, dp[5] = 2 |
| 3 | dp[3] = 1, dp[7] = 2, dp[4] = 2 |
| 2 | dp[2] = 1, dp[6] = 3, dp[7] = 3 |
| 1 | dp[7] = 4 |
| 5 | No better solution for sum 7 |
The subsequence [1,3,2,1] gives:
sum = 7
length = 4
Answer:
4
Example 3
Input
nums = [1,1,5,4,5]
target = 3
Possible sums generated:
0, 1, 2, 4, 5, 6, 9, 10, ...
Sum 3 is never reached.
Therefore:
dp[3] = -1
Answer:
-1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n × target) | Each element processes all target sums once |
| Space | O(target) | One DP array of size target + 1 |
The algorithm performs a backward scan of all sums from target down to the current number for each array element. Since there are n elements and at most target states, the total work is O(n × target).
The memory usage is only the one-dimensional DP array, requiring O(target) space.
Test Cases
sol = Solution()
assert sol.lengthOfLongestSubsequence([1,2,3,4,5], 9) == 3 # example 1
assert sol.lengthOfLongestSubsequence([4,1,3,2,1,5], 7) == 4 # example 2
assert sol.lengthOfLongestSubsequence([1,1,5,4,5], 3) == -1 # example 3
assert sol.lengthOfLongestSubsequence([5], 5) == 1 # single element equals target
assert sol.lengthOfLongestSubsequence([5], 3) == -1 # single element cannot form target
assert sol.lengthOfLongestSubsequence([1,1,1,1], 4) == 4 # use all elements
assert sol.lengthOfLongestSubsequence([1,1,1,1], 2) == 2 # multiple solutions
assert sol.lengthOfLongestSubsequence([10,20,30], 5) == -1 # all numbers too large
assert sol.lengthOfLongestSubsequence([2,3,5], 10) == 3 # entire array
assert sol.lengthOfLongestSubsequence([3,3,3,3], 6) == 2 # duplicate values
assert sol.lengthOfLongestSubsequence([1,2,2,2,2], 4) == 2 # longest among duplicates
assert sol.lengthOfLongestSubsequence([1] * 1000, 1000) == 1000 # maximum length case
Test Summary
| Test | Why |
|---|---|
[1,2,3,4,5], 9 |
Basic example with multiple valid subsequences |
[4,1,3,2,1,5], 7 |
Longest solution is not the first discovered |
[1,1,5,4,5], 3 |
No valid subsequence exists |
[5], 5 |
Single-element success case |
[5], 3 |
Single-element failure case |
[1,1,1,1], 4 |
Entire array used |
[1,1,1,1], 2 |
Multiple equivalent choices |
[10,20,30], 5 |
All values exceed target |
[2,3,5], 10 |
Whole array sums to target |
[3,3,3,3], 6 |
Duplicate values |
[1,2,2,2,2], 4 |
Competing subsequences with same sum |
[1] * 1000, 1000 |
Maximum input size and longest possible answer |
Edge Cases
No Valid Subsequence Exists
A common source of bugs is assuming every target can be formed. For example, nums = [1,1,5,4,5] and target = 3. Since no combination produces sum 3, the algorithm must return -1.
The implementation handles this naturally because impossible states remain -1 throughout the DP process. If dp[target] never changes, the answer remains -1.
Multiple Subsequences Produce the Same Target
For example:
nums = [4,1,2,3]
target = 5
Both [4,1] and [2,3] are valid. The algorithm stores the maximum length for each sum rather than merely whether the sum is achievable. This guarantees that the longest subsequence is retained.
Many Duplicate Values
Consider:
nums = [1,1,1,1]
target = 2
There are many ways to reach the target. A careless implementation could accidentally reuse the same element multiple times if it updates DP states in forward order.
The reverse iteration from target down to num ensures each array element is used at most once, preserving the subsequence constraint and producing the correct maximum length.
Target Equal to the Sum of the Entire Array
When the entire array itself forms the target, such as:
nums = [2,3,5]
target = 10
the correct answer is the full array length. The DP transitions continuously extend existing solutions, eventually building the complete subsequence and recording the maximum length correctly.
Large Input Size
With 1000 elements, any exponential solution would be impossible. The dynamic programming approach depends on the much smaller bound of target <= 1000, keeping both time and space requirements manageable even at maximum input size.