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 <= 1000Problem 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.
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.
Python
JavaScript
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.
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.
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.
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)$.
Python
Java
C++
Go
TypeScript
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
2915. Length of the Longest Subsequence That Sums to Target 🔥 || DP+Memo 🔥 || 0/1 knapsack • Ayush Rao • 1,947 views views
Watch 6 more video solutions →Practice Length of the Longest Subsequence That Sums to Target with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor