Length of the Longest Subsequence That Sums to Target

Med

#2596Time: O(n * target) due to the two nested loops iterating through `n` numbers and `target` sums.Space: O(n * target) for the 2D DP table.1 company

Patterns

Dynamic Programming

Data structures

Array

Companies

Intuit

Prompt

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 <= 1000
1 <= nums[i] <= 1000
1 <= target <= 1000

Approaches

4 approaches with complexity analysis and trade-offs.

This approach is an iterative version of the memoized recursion, often called bottom-up dynamic programming. It solves the problem by building up a solution from the smallest subproblems. This problem can be framed as a classic 0/1 Knapsack problem, where items are the numbers in nums, their 'weight' is their value, their 'value' is 1 (since we want to maximize the count), and the knapsack capacity is the target.

Algorithm

Create a 2D DP table, dp[n + 1][target + 1].
dp[i][j] will store the length of the longest subsequence using elements from nums[0...i-1] that sums to j.
Initialize the table with a value indicating impossibility, like -1.
Set the base case: dp[i][0] = 0 for all i from 0 to n, as a sum of 0 is always possible with an empty subsequence of length 0.
Iterate from i = 1 to n (for each number in nums).
Inside, iterate from j = 1 to target (for each possible sum).
For each dp[i][j], calculate the value based on two choices for nums[i-1]:
1. Don't include nums[i-1]: The length is dp[i-1][j].
2. Include nums[i-1]: If j >= nums[i-1] and dp[i-1][j - nums[i-1]] is not -1, the length is 1 + dp[i-1][j - nums[i-1]].
Set dp[i][j] to the maximum of the valid options.
The final answer is dp[n][target].

Walkthrough

We use a 2D array dp of size (n+1) x (target+1). dp[i][j] represents the maximum length of a subsequence using the first i numbers from nums that sums up to j. We fill this table iteratively. For each number nums[i-1], and for each possible sum j, we decide whether to include nums[i-1] in the subsequence or not. The value of dp[i][j] is determined by taking the maximum of these two choices: (1) the length without including the current number, which is dp[i-1][j], and (2) the length if we include the current number, which is 1 + dp[i-1][j - nums[i-1]]. The second choice is only possible if the target j is at least nums[i-1] and a valid subsequence existed for the subproblem dp[i-1][j - nums[i-1]].

1import java.util.Arrays;2import java.util.List;3 4class Solution {5    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {6        int n = nums.size();7        int[][] dp = new int[n + 1][target + 1];8 9        // Initialize dp table with -1 to indicate that a sum is not possible.10        for (int[] row : dp) {11            Arrays.fill(row, -1);12        }13 14        // Base case: a sum of 0 can always be achieved with an empty subsequence (length 0).15        for (int i = 0; i <= n; i++) {16            dp[i][0] = 0;17        }18 19        for (int i = 1; i <= n; i++) {20            int num = nums.get(i - 1);21            for (int j = 1; j <= target; j++) {22                // Option 1: Exclude the current number. The length is the same as before.23                dp[i][j] = dp[i - 1][j];24 25                // Option 2: Include the current number, if possible.26                if (j >= num && dp[i - 1][j - num] != -1) {27                    dp[i][j] = Math.max(dp[i][j], 1 + dp[i - 1][j - num]);28                }29            }30        }31 32        return dp[n][target];33    }34}

Complexity

Time

O(n * target) due to the two nested loops iterating through `n` numbers and `target` sums.

Space

O(n * target) for the 2D DP table.

Trade-offs

Pros

Avoids recursion and potential stack overflow issues.
Generally slightly faster in practice than the top-down approach due to no recursion overhead.
The logic is a clear implementation of the 0/1 Knapsack pattern.

Cons

Uses O(n * target) space, which is not optimal.

This approach explores every possible subsequence of the nums array. For each subsequence, it calculates the sum of its elements. If the sum equals the target, it compares its length with the maximum length found so far and updates it if necessary. This is done using a recursive helper function that, for each element, makes two recursive calls: one including the element in the subsequence and one excluding it.

Algorithm

Initialize a global variable maxLength to -1.
Define a recursive function solve(index, currentSum, currentLength).
Base Case: If index reaches the end of the nums array:
- If currentSum equals target, update maxLength = max(maxLength, currentLength).
- Return.
Pruning: If currentSum exceeds target, return immediately to avoid unnecessary computation.
Recursive Step: For the element at nums[index], explore two possibilities:
1. Include: Call solve(index + 1, currentSum + nums[index], currentLength + 1).
2. Exclude: Call solve(index + 1, currentSum, currentLength).
Start the process by calling solve(0, 0, 0).
Return maxLength.

Walkthrough

The brute-force method systematically generates all subsequences. A common way to do this is with recursion. We can define a function that takes the current index, the sum of the subsequence built so far, and its length. At each step, we decide whether to include the current element in our subsequence or not. This creates a binary decision tree of possibilities. When we've considered all elements (i.e., reached the end of the array), we check if the subsequence's sum matches the target. If it does, we update our answer with the length of this subsequence if it's the longest one seen yet.

1import java.util.List;2 3class Solution {4    private int maxLength = -1;5 6    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {7        solve(nums, 0, 0, 0);8        return maxLength;9    }10 11    private void solve(List<Integer> nums, int index, int currentSum, int currentLength) {12        // Base case: we have considered all elements13        if (index == nums.size()) {14            if (currentSum == target) {15                maxLength = Math.max(maxLength, currentLength);16            }17            return;18        }19 20        // Pruning: if sum exceeds target, no need to proceed further21        if (currentSum > target) {22            return;23        }24 25        // Recursive step:26        // Option 1: Include the current element nums.get(index)27        solve(nums, index + 1, currentSum + nums.get(index), currentLength + 1);28 29        // Option 2: Exclude the current element nums.get(index)30        solve(nums, index + 1, currentSum, currentLength);31    }32}

Complexity

Time

O(2^n), where `n` is the number of elements in `nums`. For each element, we make two choices (include or exclude), leading to an exponential number of paths to explore.

Space

O(n), where `n` is the number of elements in `nums`. This space is used by the recursion call stack, which can go as deep as `n`.

Trade-offs

Pros

Simple to understand and implement.
It's a direct translation of the problem definition.

Cons

Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.

The brute-force recursive solution involves many redundant calculations for the same subproblems (i.e., same index and same remaining target). We can optimize this by using memoization, a top-down dynamic programming technique. We store the results of subproblems in a cache (e.g., a 2D array) so that we don't have to recompute them. A subproblem can be uniquely identified by the current index and the remaining target sum.

Algorithm

Define a recursive function solve(index, currentTarget) that returns the max length of a subsequence from nums[index:] summing to currentTarget.
Use a 2D array memo[n][target + 1] to store the results of subproblems, initialized with a value indicating 'not computed' (e.g., null or a special integer).
Base Cases:
- If currentTarget == 0, return 0 (target reached).
- If index >= n or currentTarget < 0, return a large negative number to signify failure.
Memoization Check: Before computing, check if memo[index][currentTarget] has a stored value. If so, return it.
Recursive Step: Calculate the maximum length by considering two choices:
1. Include nums[index]: 1 + solve(index + 1, currentTarget - nums[index]).
2. Exclude nums[index]: solve(index + 1, currentTarget).
Store the result max(include, exclude) in memo[index][currentTarget] before returning.
The initial call is solve(0, target). If the result is negative, no solution exists; otherwise, the result is the answer.

Walkthrough

This approach refines the recursive solution by adding a memory component. The state of our recursion is defined by (index, target). We create a 2D array, memo, where memo[index][target] will store the answer for the subproblem of finding the longest subsequence in nums from index onwards that sums to target. Before any computation, the function checks if the answer for the current state is already in the memo table. If it is, it returns the stored value. Otherwise, it computes the result, stores it in the table, and then returns it. This ensures that each subproblem is solved only once.

1import java.util.List;2 3class Solution {4    private Integer[][] memo;5    private List<Integer> nums;6    private int n;7 8    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {9        this.n = nums.size();10        this.nums = nums;11        this.memo = new Integer[n][target + 1];12        int result = solve(0, target);13        // If result is negative, it means no such subsequence was found.14        return result < 0 ? -1 : result;15    }16 17    private int solve(int index, int currentTarget) {18        if (currentTarget == 0) {19            return 0;20        }21        if (index >= n || currentTarget < 0) {22            // Use a large negative number to represent an impossible path.23            return -1001; 24        }25        if (memo[index][currentTarget] != null) {26            return memo[index][currentTarget];27        }28 29        // Case 1: Include nums.get(index)30        int include = 1 + solve(index + 1, currentTarget - nums.get(index));31 32        // Case 2: Exclude nums.get(index)33        int exclude = solve(index + 1, currentTarget);34 35        return memo[index][currentTarget] = Math.max(include, exclude);36    }37}

Complexity

Time

O(n * target). The number of unique subproblems is `n * target`, and each is solved exactly once.

Space

O(n * target). This is for the memoization table. The recursion stack also adds O(n) space, but it's dominated by the table.

Trade-offs

Pros

Drastically improves performance over brute force by avoiding re-computation.
Guaranteed to run in pseudo-polynomial time, which is efficient enough for the given constraints.
Often more intuitive to write than the bottom-up iterative version.

Cons

Requires O(n * target) space, which can be substantial for large n and target.
Recursive solutions might lead to a stack overflow for very deep recursion trees, although it's unlikely with the given constraints.

We can observe that the calculation of the current row dp[i] in the bottom-up approach only depends on the values from the previous row dp[i-1]. This dependency allows us to optimize the space complexity significantly by using only a single 1D array instead of a 2D table. This is the most efficient approach for this problem in terms of both time and space.

Algorithm

Create a 1D DP array, dp of size target + 1.
dp[j] will store the length of the longest subsequence that sums to j.
Initialize dp[0] = 0 and all other elements to -1 (or another sentinel for impossibility).
Iterate through each number num in the nums array.
For each num, update the dp array by iterating the sum j from target down to num.
The update rule is: dp[j] = max(dp[j], 1 + dp[j - num]), but only if dp[j - num] is not -1 (i.e., the subproblem was solvable).
The backward iteration for j is crucial. It ensures that dp[j - num] reflects the state before considering the current num, thus preventing the same element from being used multiple times to form one subsequence.
After iterating through all numbers, dp[target] will hold the final answer.

Walkthrough

This approach optimizes the space of the bottom-up DP. Instead of a 2D table, we use a 1D array dp of size target + 1. dp[j] will store the maximum length of a subsequence that sums to j using the numbers considered so far. We iterate through each number in nums. For each number, we update the dp array. The key insight is to iterate the inner loop (for the target sums) backwards, from target down to the current number's value. This prevents us from using the same number multiple times within the same subsequence. If we were to iterate forwards, dp[j] would be computed using a dp[j - num] that might have already been updated with the current num, which would be incorrect for a subsequence problem (it would solve the 'unbounded knapsack' variant).

1import java.util.Arrays;2import java.util.List;3 4class Solution {5    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {6        int[] dp = new int[target + 1];7        // Initialize with -1 to signify that a sum is not reachable.8        Arrays.fill(dp, -1);9        // Base case: a sum of 0 is reachable with an empty subsequence of length 0.10        dp[0] = 0;11 12        for (int num : nums) {13            // Iterate backwards to prevent using the same element multiple times in one subsequence.14            for (int j = target; j >= num; j--) {15                // If we can form a sum of (j - num), we can try to form a sum of j.16                if (dp[j - num] != -1) {17                    // We either keep the existing length for sum j, or we form a new, potentially longer one.18                    dp[j] = Math.max(dp[j], 1 + dp[j - num]);19                }20            }21        }22 23        return dp[target];24    }25}

Complexity

Time

O(n * target). The time complexity remains the same as the unoptimized DP, with two nested loops.

Space

O(target). We only need a 1D array of size `target + 1`.

Trade-offs

Pros

Most efficient solution in terms of space complexity.
Maintains the optimal O(n * target) time complexity.

Cons

The logic of the inner loop iterating backwards can be slightly less intuitive at first glance compared to the 2D DP approach.

Solutions

Solution

1class Solution { public int lengthOfLongestSubsequence ( List < Integer > nums , int target ) { int n = nums . size (); int [][] f = new int [ n + 1 ][ target + 1 ]; final int inf = 1 << 30 ; for ( int [] g : f ) { Arrays . fill ( g , - inf ); } f [ 0 ][ 0 ] = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { int x = nums . get ( i - 1 ); for ( int j = 0 ; j <= target ; ++ j ) { f [ i ][ j ] = f [ i - 1 ][ j ]; if ( j >= x ) { f [ i ][ j ] = Math . max ( f [ i ][ j ], f [ i - 1 ][ j - x ] + 1 ); } } } return f [ n ][ target ] <= 0 ? - 1 : f [ n ][ target ]; } }

1class Solution { public: int lengthOfLongestSubsequence ( vector < int >& nums , int target ) { int n = nums . size (); int f [ n + 1 ][ target + 1 ]; memset ( f , - 0x3f , sizeof ( f )); f [ 0 ][ 0 ] = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { int x = nums [ i - 1 ]; for ( int j = 0 ; j <= target ; ++ j ) { f [ i ][ j ] = f [ i - 1 ][ j ]; if ( j >= x ) { f [ i ][ j ] = max ( f [ i ][ j ], f [ i - 1 ][ j - x ] + 1 ); } } } return f [ n ][ target ] <= 0 ? - 1 : f [ n ][ target ]; } };

1class 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 ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution { public int lengthOfLongestSubsequence ( List < Integer > nums , int target ) { int n = nums . size (); int [][] f = new int [ n + 1 ][ target + 1 ]; final int inf = 1 << 30 ; for ( int [] g : f ) { Arrays . fill ( g , - inf ); } f [ 0 ][ 0 ] = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { int x = nums . get ( i - 1 ); for ( int j = 0 ; j <= target ; ++ j ) { f [ i ][ j ] = f [ i - 1 ][ j ]; if ( j >= x ) { f [ i ][ j ] = Math . max ( f [ i ][ j ], f [ i - 1 ][ j - x ] + 1 ); } } } return f [ n ][ target ] <= 0 ? - 1 : f [ n ][ target ]; } }

1class Solution { public: int lengthOfLongestSubsequence ( vector < int >& nums , int target ) { int n = nums . size (); int f [ n + 1 ][ target + 1 ]; memset ( f , - 0x3f , sizeof ( f )); f [ 0 ][ 0 ] = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { int x = nums [ i - 1 ]; for ( int j = 0 ; j <= target ; ++ j ) { f [ i ][ j ] = f [ i - 1 ][ j ]; if ( j >= x ) { f [ i ][ j ] = max ( f [ i ][ j ], f [ i - 1 ][ j - x ] + 1 ); } } } return f [ n ][ target ] <= 0 ? - 1 : f [ n ][ target ]; } };

1class 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 ]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.