# Length of the Longest Subsequence That Sums to Target
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/length-of-the-longest-subsequence-that-sums-to-target)
Canonical: https://scaleengineer.com/dsa/problems/length-of-the-longest-subsequence-that-sums-to-target
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit)
---
## Problem
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
## Brute Force using Recursion
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.
**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`.
**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.
### Explanation
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.

```java
import java.util.List;

class Solution {
    private int maxLength = -1;

    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
        solve(nums, 0, 0, 0);
        return maxLength;
    }

    private void solve(List<Integer> nums, int index, int currentSum, int currentLength) {
        // Base case: we have considered all elements
        if (index == nums.size()) {
            if (currentSum == target) {
                maxLength = Math.max(maxLength, currentLength);
            }
            return;
        }

        // Pruning: if sum exceeds target, no need to proceed further
        if (currentSum > target) {
            return;
        }

        // Recursive step:
        // Option 1: Include the current element nums.get(index)
        solve(nums, index + 1, currentSum + nums.get(index), currentLength + 1);

        // Option 2: Exclude the current element nums.get(index)
        solve(nums, index + 1, currentSum, currentLength);
    }
}
```
### 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`.

## Top-Down Dynamic Programming with Memoization
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.
**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.
**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.
### Explanation
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.

```java
import java.util.List;

class Solution {
    private Integer[][] memo;
    private List<Integer> nums;
    private int n;

    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
        this.n = nums.size();
        this.nums = nums;
        this.memo = new Integer[n][target + 1];
        int result = solve(0, target);
        // If result is negative, it means no such subsequence was found.
        return result < 0 ? -1 : result;
    }

    private int solve(int index, int currentTarget) {
        if (currentTarget == 0) {
            return 0;
        }
        if (index >= n || currentTarget < 0) {
            // Use a large negative number to represent an impossible path.
            return -1001; 
        }
        if (memo[index][currentTarget] != null) {
            return memo[index][currentTarget];
        }

        // Case 1: Include nums.get(index)
        int include = 1 + solve(index + 1, currentTarget - nums.get(index));

        // Case 2: Exclude nums.get(index)
        int exclude = solve(index + 1, currentTarget);

        return memo[index][currentTarget] = Math.max(include, exclude);
    }
}
```
### 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.

## 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`.
**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.
**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.
### Explanation
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]]`.

```java
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];
    }
}
```
### 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]`.

## Space-Optimized Bottom-Up Dynamic Programming
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.
**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`.
**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.
### Explanation
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).

```java
import java.util.Arrays;
import java.util.List;

class Solution {
    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
        int[] dp = new int[target + 1];
        // Initialize with -1 to signify that a sum is not reachable.
        Arrays.fill(dp, -1);
        // Base case: a sum of 0 is reachable with an empty subsequence of length 0.
        dp[0] = 0;

        for (int num : nums) {
            // Iterate backwards to prevent using the same element multiple times in one subsequence.
            for (int j = target; j >= num; j--) {
                // If we can form a sum of (j - num), we can try to form a sum of j.
                if (dp[j - num] != -1) {
                    // We either keep the existing length for sum j, or we form a new, potentially longer one.
                    dp[j] = Math.max(dp[j], 1 + dp[j - num]);
                }
            }
        }

        return dp[target];
    }
}
```
### 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.

# Solutions
### Java

```java
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 ]; } }
```

### CPP

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

### Python

```python
class 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 ]
```