Length of the Longest Subsequence That Sums to Target - Solution & Explanation
Problem Statement
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.
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 <= 10001 <= nums[i] <= 10001 <= target <= 1000
Approach Overview
Problem Overview: Given an integer array nums and a target value, find the maximum length of a subsequence whose elements add up exactly to the target. If no subsequence produces the target sum, return -1. The order of elements must follow the original array, but you can skip any elements.
Approach 1: Brute Force with Subset Generation (O(2^n) time, O(n) space)
Generate every possible subsequence and compute its sum. This can be implemented using recursion or bitmask enumeration. For each subsequence, track both the current sum and the number of elements used. Whenever the sum equals target, update the maximum length found. This approach explores the entire decision tree of including or excluding each element, which results in 2^n combinations. It works only for very small arrays but helps verify correctness and understand the search space.
Approach 2: Dynamic Programming (Knapsack-like) (O(n * target) time, O(target) space)
This problem behaves like a variation of the classic 0/1 knapsack. Instead of maximizing value, you maximize subsequence length while achieving a specific sum. Maintain a DP array dp[t] representing the maximum subsequence length that produces sum t. Initialize dp[0] = 0 and all other values as negative infinity (or an invalid state). Iterate through the numbers in nums, and for each value update the DP array from target down to the current number. The transition is dp[t] = max(dp[t], dp[t - num] + 1). Reverse iteration prevents reusing the same element multiple times. After processing all elements, dp[target] stores the length of the longest valid subsequence, or remains invalid if no combination forms the target.
This method efficiently compresses the exponential search space into a polynomial dynamic programming solution. The technique appears frequently in dynamic programming problems that resemble subset-sum or knapsack patterns on an array.
Recommended for interviews: The dynamic programming solution is the expected approach. Interviewers want to see recognition of the subset-sum / knapsack pattern and the use of a 1D DP array with reverse iteration. Mentioning the brute force subset generation first demonstrates understanding of the problem space, but implementing the DP optimization shows stronger algorithmic skill.
Approach 1: Approach 1: Brute Force with Subset Generation
This approach involves generating all possible subsequences of the given list, computing their sums, and checking if any subsequence sums to the target. If multiple subsequences match the target, we find the length of the longest one.
We can achieve this using recursive backtracking, where for each element, we have the choice to include it in the current subsequence or exclude it. This will give us a power set (all possible subsets) to consider.
This solution uses a recursive depth-first search (DFS) approach to check all subsequences. We use a helper function to explore all possibilities by either including or excluding the current element. The base case stores the length of the subsequence if it matches the target and updates the maximum length found so far.
Code
Python
JavaScript
Complexity
Time Complexity: O(2^n), where n is the number of elements in the input array nums. This is because we generate all possible subsequences.
Space Complexity: O(n) for the recursion stack.
Approach 2: Approach 2: Dynamic Programming (Knapsack-like)
This approach utilizes a dynamic programming technique reminiscent of the knapsack problem. We maintain a DP array where the entry at index 'i' holds the maximum length of a subsequence that sums to 'i'. For each number in the list, you can update the DP entries based on whether including the current number leads to a new maximum subsequence length for a specific sum.
The dynamic programming approach works by iteratively updating a DP array for each number. For every potential target sum from target down to the number, we check if the preceding target was achievable and update the current entry with the new potential subsequence length.
Complexity
Time Complexity: O(n * target), where n is the number of elements in nums.
Space Complexity: O(target), as we use an array of size target + 1 to store results for subproblems.
Approach 3: 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.
For f[i][j], we consider the ith number x. If we do not select x, then f[i][j]=f[i-1][j]. If we select x, then f[i][j]=f[i-1][j-x]+1, where j\ge x. Therefore, we have the state transition equation:
$
f[i][j]=max{f[i-1][j],f[i-1][j-x]+1}
The final answer is f[n][target]. If f[n][target]\le0, there is no subsequence with a sum of target, return -1.
The time complexity is O(ntimes target), and the space complexity is O(ntimes target). Here, n is the length of the array, and target is the target value.
We notice that the state of f[i][j] is only related to f[i-1][cdot], so we can optimize the first dimension and reduce the space complexity to O(target)$.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force with Subset Generation | Time Complexity: O(2^n), where n is the number of elements in the input array nums. This is because we generate all possible subsequences. Space Complexity: O(n) for the recursion stack. |
| Approach 2: Dynamic Programming (Knapsack-like) | Time Complexity: O(n * target), where n is the number of elements in nums. Space Complexity: O(target), as we use an array of size target + 1 to store results for subproblems. |
| Dynamic Programming | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Generation | O(2^n) | O(n) | Small input sizes or when demonstrating the baseline solution during interviews |
| Dynamic Programming (Knapsack-like) | O(n * target) | O(target) | General case and interview-expected solution for subset-sum style problems |
Video Solution
2915. Length of the Longest Subsequence That Sums to Target 🔥 || DP+Memo 🔥 || 0/1 knapsack • Ayush Rao • 2,008 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Length of the Longest Subsequence That Sums to Target easy or hard?
Length of the Longest Subsequence That Sums to Target Python/Java solution
How to solve Length of the Longest Subsequence That Sums to Target in O(n)?
What is the best approach for Length of the Longest Subsequence That Sums to Target?
Is Length of the Longest Subsequence That Sums to Target asked at Google/Amazon/Meta?
What data structure is used in Length of the Longest Subsequence That Sums to Target?
What is the time complexity of Length of the Longest Subsequence That Sums to Target?
Ready to solve this problem?
Practice Length of the Longest Subsequence That Sums to Target with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor