Watch 7 video solutions for Length of the Longest Subsequence That Sums to Target, a medium level problem involving Array, Dynamic Programming. This walkthrough by Ayush Rao has 1,947 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |