Scale Engineer

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]].

import java.util.Arrays;import java.util.List; class Solution {    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {        int n = nums.size();        int[][] dp = new int[n + 1][target + 1];         // Initialize dp table with -1 to indicate that a sum is not possible.        for (int[] row : dp) {            Arrays.fill(row, -1);        }         // Base case: a sum of 0 can always be achieved with an empty subsequence (length 0).        for (int i = 0; i <= n; i++) {            dp[i][0] = 0;        }         for (int i = 1; i <= n; i++) {            int num = nums.get(i - 1);            for (int j = 1; j <= target; j++) {                // Option 1: Exclude the current number. The length is the same as before.                dp[i][j] = dp[i - 1][j];                 // Option 2: Include the current number, if possible.                if (j >= num && dp[i - 1][j - num] != -1) {                    dp[i][j] = Math.max(dp[i][j], 1 + dp[i - 1][j - num]);                }            }        }         return dp[n][target];    }}

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.

Solutions

class 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 ]; } }

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 →

Next problem