Length of the longest subsequence that sums to target

Array Dynamic Programming

39.3% acceptance

Feb 25, 2026

298

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn length_of_longest_subsequence(nums: Vec<i32>, target: i32) -> i32 {
    let t = target as usize;
    // dp[s] = max length of subsequence with sum s, -inf if not reachable
    let mut dp = vec![i32::MIN; t + 1];
    dp[0] = 0;
    for &x in &nums {
      let x = x as usize;
      if x > t { continue; }
      for s in (x..=t).rev() {
        if dp[s - x] != i32::MIN {
          dp[s] = dp[s].max(dp[s - x] + 1);
        }
      }
    }
    if dp[t] < 0 { -1 } else { dp[t] }
  }
}