Problem Description

You are given an array of integers nums (0-indexed) and an integer target. Your task is to find the length of the longest subsequence from nums that adds up to exactly target.

A subsequence is formed by selecting elements from the original array while maintaining their relative order. You can choose to include or exclude any element, but you cannot rearrange them.

For example:

• If nums = [1, 2, 3, 4] and target = 5, you could select [1, 4] or [2, 3] to get a sum of 5
• The subsequence [1, 4] has length 2, and [2, 3] also has length 2
• Both are valid subsequences since they maintain the original order

The goal is to find the maximum possible length among all subsequences that sum to target. If no subsequence can sum to target, return -1.

The solution uses dynamic programming where f[i][j] represents the maximum length of a subsequence using the first i elements that sum to exactly j. For each element, we decide whether to include it or not:

• If we don't include element x, then f[i][j] = f[i-1][j]
• If we include element x, then f[i][j] = f[i-1][j-x] + 1 (when j >= x)

The state transition equation is: f[i][j] = max{f[i-1][j], f[i-1][j-x] + 1}

The algorithm initializes f[0][0] = 0 (empty subsequence sums to 0) and all other values to negative infinity. After processing all elements, f[n][target] gives the answer. If this value is less than or equal to 0, no valid subsequence exists, so we return -1.

Intuition

The key insight is recognizing this as a variant of the classic knapsack problem. We want to find the maximum number of items (elements) we can pick that sum to exactly a target value.

Think about building up solutions incrementally. For any position in the array and any possible sum, we need to track the maximum length subsequence that can achieve that sum. This naturally leads to a dynamic programming approach.

Consider how we make decisions for each element: we either include it in our subsequence or we don't. If we've already computed the best ways to achieve various sums using previous elements, we can extend those solutions by potentially adding the current element.

The state representation f[i][j] emerges from asking: "What's the longest subsequence I can form using the first i elements that sums to exactly j?" This question captures both constraints we need to satisfy - the sum requirement and the length maximization.

Why initialize with negative infinity? We need to distinguish between "impossible to achieve this sum" and "achievable with 0 elements" (which is only true for sum = 0). Using negative infinity for impossible states ensures that when we try to build upon them (by adding 1 for including an element), they remain negative, signaling impossibility.

The decision at each step is straightforward: for each possible sum j, we compare:

• Not taking the current element: inherit the best solution from previous elements for the same sum
• Taking the current element (if possible): take the best solution for sum j - x from previous elements and add 1 to the length

This bottom-up construction guarantees we consider all valid subsequences and track the longest one for each possible sum, ultimately giving us the answer for our target sum.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement a 2D dynamic programming solution where f[i][j] represents the maximum length of a subsequence using the first i elements that sum to exactly j.

Initialization:

• Create a 2D array f of size (n+1) × (target+1) where n is the length of nums
• Initialize all values to negative infinity (-inf) to represent impossible states
• Set f[0][0] = 0 since an empty subsequence has sum 0 and length 0

State Transition: For each element x at position i (1-indexed) and each possible sum j from 0 to target:

1. Option 1 - Don't include current element:

   • f[i][j] = f[i-1][j]
   • We inherit the best solution from the previous state

2. Option 2 - Include current element (if j >= x):

   • f[i][j] = max(f[i][j], f[i-1][j-x] + 1)
   • We take the best solution for sum j-x using previous elements and add 1 to the length
   • This is only valid when j >= x (we can't achieve a negative sum)

Implementation Details:

for i, x in enumerate(nums, 1):  # Process each element
    for j in range(target + 1):   # For each possible sum
        f[i][j] = f[i - 1][j]     # Don't take current element
        if j >= x:                 # Can we take current element?
            f[i][j] = max(f[i][j], f[i - 1][j - x] + 1)

Final Answer:

• Check f[n][target] which contains the maximum length for sum equal to target
• If f[n][target] <= 0, no valid subsequence exists, return -1
• Otherwise, return f[n][target]

The time complexity is O(n × target) as we fill a 2D table of this size. The space complexity is also O(n × target) for storing the DP table.

Example Walkthrough

Let's walk through a concrete example with nums = [1, 2, 3, 4] and target = 5.

We'll build a DP table f[i][j] where i represents using the first i elements, and j represents the target sum.

Initial Setup:

• Array: [1, 2, 3, 4], Target: 5
• Table size: 5 × 6 (including row/column for 0)
• Initialize all values to -∞, except f[0][0] = 0

Initial Table:

    j: 0   1   2   3   4   5
i:0    0  -∞  -∞  -∞  -∞  -∞
  1   -∞  -∞  -∞  -∞  -∞  -∞
  2   -∞  -∞  -∞  -∞  -∞  -∞
  3   -∞  -∞  -∞  -∞  -∞  -∞
  4   -∞  -∞  -∞  -∞  -∞  -∞

Processing element 1 (value = 1): For each sum j from 0 to 5:

• j=0: Don't take 1: f[1][0] = f[0][0] = 0
• j=1: Take 1: f[1][1] = max(f[0][1], f[0][0] + 1) = max(-∞, 0 + 1) = 1
• j=2 to 5: Can only inherit -∞ from above

    j: 0   1   2   3   4   5
i:0    0  -∞  -∞  -∞  -∞  -∞
  1    0   1  -∞  -∞  -∞  -∞

Processing element 2 (value = 2):

• j=0: f[2][0] = 0 (don't take anything)
• j=1: f[2][1] = 1 (use just [1])
• j=2: f[2][2] = max(f[1][2], f[1][0] + 1) = max(-∞, 0 + 1) = 1 (use [2])
• j=3: f[2][3] = max(f[1][3], f[1][1] + 1) = max(-∞, 1 + 1) = 2 (use [1,2])
• j=4,5: Remain -∞

    j: 0   1   2   3   4   5
i:0    0  -∞  -∞  -∞  -∞  -∞
  1    0   1  -∞  -∞  -∞  -∞
  2    0   1   1   2  -∞  -∞

Processing element 3 (value = 3):

• j=0: f[3][0] = 0
• j=1: f[3][1] = 1 (use [1])
• j=2: f[3][2] = 1 (use [2])
• j=3: f[3][3] = max(2, f[2][0] + 1) = max(2, 1) = 2 (use [1,2])
• j=4: f[3][4] = max(-∞, f[2][1] + 1) = 2 (use [1,3])
• j=5: f[3][5] = max(-∞, f[2][2] + 1) = 2 (use [2,3])

    j: 0   1   2   3   4   5
i:0    0  -∞  -∞  -∞  -∞  -∞
  1    0   1  -∞  -∞  -∞  -∞
  2    0   1   1   2  -∞  -∞
  3    0   1   1   2   2   2

Processing element 4 (value = 4):

• j=0: f[4][0] = 0
• j=1: f[4][1] = 1 (use [1])
• j=2: f[4][2] = 1 (use [2])
• j=3: f[4][3] = 2 (use [1,2])
• j=4: f[4][4] = max(2, f[3][0] + 1) = max(2, 1) = 2 (use [1,3] or [4])
• j=5: f[4][5] = max(2, f[3][1] + 1) = max(2, 2) = 2 (use [2,3] or [1,4])

Final Table:

    j: 0   1   2   3   4   5
i:0    0  -∞  -∞  -∞  -∞  -∞
  1    0   1  -∞  -∞  -∞  -∞
  2    0   1   1   2  -∞  -∞
  3    0   1   1   2   2   2
  4    0   1   1   2   2   2

Result: f[4][5] = 2, so the longest subsequence that sums to 5 has length 2. This corresponds to subsequences like [1,4] or [2,3].

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n * target), where n is the length of the input array nums. This is because we have two nested loops: the outer loop iterates through all n elements in nums, and the inner loop iterates through all possible sums from 0 to target. For each combination of i and j, we perform constant time operations.

The space complexity of the code is O(n * target). We create a 2D DP table f with dimensions (n + 1) × (target + 1) to store the maximum length of subsequences for each state.

However, as mentioned in the reference answer, since f[i][j] only depends on f[i-1][j] and f[i-1][j-x] (values from the previous row), we can optimize the space complexity. Instead of maintaining the entire 2D table, we could use a 1D array of size target + 1 and update it in-place, reducing the space complexity to O(target).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Initialization of Impossible States

A common mistake is initializing the DP table with 0 instead of negative infinity. This leads to incorrect results when no valid subsequence exists.

Wrong approach:

dp = [[0] * (target + 1) for _ in range(n + 1)]

Why it's wrong: With 0 initialization, dp[i][j] = 0 could mean either:

• A valid empty subsequence (correct only for dp[0][0])
• An impossible state where no subsequence sums to j

This ambiguity causes the algorithm to incorrectly compute transitions. For example, if we can't form sum j-num with previous elements, dp[i-1][j-num] would be 0, and dp[i-1][j-num] + 1 would give 1, falsely indicating we can form sum j with length 1.

Correct approach:

dp = [[-float('inf')] * (target + 1) for _ in range(n + 1)]
dp[0][0] = 0  # Only valid initial state

2. Space Optimization Breaking Logic

When optimizing space to use a 1D array, a common mistake is updating values in the wrong order, causing elements to be used multiple times.

Wrong space-optimized approach:

dp = [-float('inf')] * (target + 1)
dp[0] = 0
for num in nums:
    for j in range(num, target + 1):  # Forward iteration - WRONG!
        dp[j] = max(dp[j], dp[j - num] + 1)

Why it's wrong: Forward iteration causes dp[j - num] to potentially use the already-updated value from the current iteration, allowing the same element to be selected multiple times.

Correct space-optimized approach:

dp = [-float('inf')] * (target + 1)
dp[0] = 0
for num in nums:
    for j in range(target, num - 1, -1):  # Backward iteration - CORRECT!
        dp[j] = max(dp[j], dp[j - num] + 1)

3. Forgetting to Handle Edge Cases

Not properly checking if the final result is valid before returning.

Wrong approach:

return dp[n][target]  # Might return negative infinity

Correct approach:

return -1 if dp[n][target] <= 0 else dp[n][target]

4. Integer Overflow with Large Negative Values

In some languages, using Integer.MIN_VALUE for initialization can cause overflow when adding 1.

Solution: Use a sufficiently large negative value like -1e9 or handle the impossible state check explicitly:

if dp[i-1][j-num] == -float('inf'):
    continue  # Skip impossible transitions
dp[i][j] = max(dp[i][j], dp[i-1][j-num] + 1)