Problem

You are given a 0-indexed array of integers nums, and an integer target.

Return thelength 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.

Examples

Example 1

1
2
3

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

1
2
3

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

1
2
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

Solution

Method 1 – Dynamic Programming (Subset Sum with Length Tracking)

Intuition

We want the longest subsequence whose sum is exactly target. This is a variant of the subset sum problem, but instead of just checking if a sum is possible, we track the maximum length for each possible sum using dynamic programming.

Approach

  1. Use a dictionary (or array) dp where dp[s] is the maximum length of a subsequence that sums to s.
  2. Initialize dp[0] = 0 (empty subsequence has sum 0 and length 0).
  3. For each number in nums, for each sum in dp (iterate in reverse to avoid using the same number twice), update dp[s+num] = max(dp[s+num], dp[s]+1).
  4. After processing all numbers, if target is in dp, return dp[target], else return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        unordered_map<int, int> dp;
        dp[0] = 0;
        for (int x : nums) {
            auto cur = dp;
            for (auto& [s, l] : cur) {
                int ns = s + x;
                if (ns <= target)
                    dp[ns] = max(dp.count(ns) ? dp[ns] : -1, l + 1);
            }
        }
        return dp.count(target) ? dp[target] : -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func lengthOfLongestSubsequence(nums []int, target int) int {
    dp := map[int]int{0: 0}
    for _, x := range nums {
        cur := make(map[int]int)
        for k, v := range dp { cur[k] = v }
        for s, l := range cur {
            ns := s + x
            if ns <= target {
                if dp[ns] < l+1 { dp[ns] = l+1 }
            }
        }
    }
    if v, ok := dp[target]; ok { return v }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int lengthOfLongestSubsequence(int[] nums, int target) {
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(0, 0);
        for (int x : nums) {
            Map<Integer, Integer> cur = new HashMap<>(dp);
            for (var e : cur.entrySet()) {
                int ns = e.getKey() + x;
                if (ns <= target)
                    dp.put(ns, Math.max(dp.getOrDefault(ns, -1), e.getValue() + 1));
            }
        }
        return dp.containsKey(target) ? dp.get(target) : -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun lengthOfLongestSubsequence(nums: IntArray, target: Int): Int {
        val dp = mutableMapOf(0 to 0)
        for (x in nums) {
            val cur = dp.toMap()
            for ((s, l) in cur) {
                val ns = s + x
                if (ns <= target)
                    dp[ns] = maxOf(dp.getOrDefault(ns, -1), l + 1)
            }
        }
        return dp[target] ?: -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def lengthOfLongestSubsequence(self, nums: list[int], target: int) -> int:
        dp: dict[int, int] = {0: 0}
        for x in nums:
            cur = dp.copy()
            for s, l in cur.items():
                ns = s + x
                if ns <= target:
                    dp[ns] = max(dp.get(ns, -1), l + 1)
        return dp.get(target, -1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn length_of_longest_subsequence(nums: Vec<i32>, target: i32) -> i32 {
        use std::collections::HashMap;
        let mut dp = HashMap::new();
        dp.insert(0, 0);
        for &x in &nums {
            let cur = dp.clone();
            for (&s, &l) in &cur {
                let ns = s + x;
                if ns <= target {
                    dp.insert(ns, dp.get(&ns).copied().unwrap_or(-1).max(l + 1));
                }
            }
        }
        *dp.get(&target).unwrap_or(&-1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    lengthOfLongestSubsequence(nums: number[], target: number): number {
        const dp = new Map<number, number>();
        dp.set(0, 0);
        for (const x of nums) {
            const cur = new Map(dp);
            for (const [s, l] of cur) {
                const ns = s + x;
                if (ns <= target)
                    dp.set(ns, Math.max(dp.get(ns) ?? -1, l + 1));
            }
        }
        return dp.get(target) ?? -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n*target), where n is the length of nums and target is the sum limit (in the worst case, all sums up to target are possible).
  • 🧺 Space complexity: O(target), for the dp dictionary.