Length of the Longest Subsequence That Sums to Target

MEDIUM

Description

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

Checkout 4 different approaches to solve Length of the Longest Subsequence That Sums to Target. Click on different approaches to view the approach and algorithm in detail.

Bottom-Up Dynamic Programming

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

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 Analysis

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

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Length of the Longest Subsequence That Sums to Target. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Length of the Longest Subsequence That Sums to Target

Patterns:

Dynamic Programming

Data Structures:

Array

Companies:

Intuit |