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

Use a dictionary (or array) dp where dp[s] is the maximum length of a subsequence that sums to s.
Initialize dp[0] = 0 (empty subsequence has sum 0 and length 0).
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).
After processing all numbers, if target is in dp, return dp[target], else return -1.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int lengthOfLongestSubsequence(vector<int>& nums, int target) {\n        unordered_map<int, int> dp;\n        dp[0] = 0;\n        for (int x : nums) {\n            auto cur = dp;\n            for (auto& [s, l] : cur) {\n                int ns = s + x;\n                if (ns <= target)\n                    dp[ns] = max(dp.count(ns) ? dp[ns] : -1, l + 1);\n            }\n        }\n        return dp.count(target) ? dp[target] : -1;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func lengthOfLongestSubsequence(nums []int, target int) int {\n    dp := map[int]int{0: 0}\n    for _, x := range nums {\n        cur := make(map[int]int)\n        for k, v := range dp { cur[k] = v }\n        for s, l := range cur {\n            ns := s + x\n            if ns <= target {\n                if dp[ns] < l+1 { dp[ns] = l+1 }\n            }\n        }\n    }\n    if v, ok := dp[target]; ok { return v }\n    return -1\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int lengthOfLongestSubsequence(int[] nums, int target) {\n        Map<Integer, Integer> dp = new HashMap<>();\n        dp.put(0, 0);\n        for (int x : nums) {\n            Map<Integer, Integer> cur = new HashMap<>(dp);\n            for (var e : cur.entrySet()) {\n                int ns = e.getKey() + x;\n                if (ns <= target)\n                    dp.put(ns, Math.max(dp.getOrDefault(ns, -1), e.getValue() + 1));\n            }\n        }\n        return dp.containsKey(target) ? dp.get(target) : -1;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun lengthOfLongestSubsequence(nums: IntArray, target: Int): Int {\n        val dp = mutableMapOf(0 to 0)\n        for (x in nums) {\n            val cur = dp.toMap()\n            for ((s, l) in cur) {\n                val ns = s + x\n                if (ns <= target)\n                    dp[ns] = maxOf(dp.getOrDefault(ns, -1), l + 1)\n            }\n        }\n        return dp[target] ?: -1\n    }\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n    def lengthOfLongestSubsequence(self, nums: list[int], target: int) -> int:\n        dp: dict[int, int] = {0: 0}\n        for x in nums:\n            cur = dp.copy()\n            for s, l in cur.items():\n                ns = s + x\n                if ns <= target:\n                    dp[ns] = max(dp.get(ns, -1), l + 1)\n        return dp.get(target, -1)","lang":"python"},{"language":"Rust","code":"impl Solution {\n    pub fn length_of_longest_subsequence(nums: Vec<i32>, target: i32) -> i32 {\n        use std::collections::HashMap;\n        let mut dp = HashMap::new();\n        dp.insert(0, 0);\n        for &x in &nums {\n            let cur = dp.clone();\n            for (&s, &

Related Tags