easy to understand solution || beginner friendly
\n\n### Intuition\nTo solve the problem of finding the length of the longest subsequence that sums up to a given target, we can use dynamic programming. The mai
\n\n### Intuition\nTo solve the problem of finding the length of the longest subsequence that sums up to a given target, we can use dynamic programming. The main idea is to recursively explore all possible subsets of the given array and check if their sum equals the target. At each step, we either include the current element or skip it, while keeping track of the length of the valid subsequence. Memoization helps to avoid redundant calculations.\n\n### Approach\n1. **Recursive Function**: The function `subsetSum(arr, i, target, dp)` recursively checks whether it\'s possible to get a sum equal to `target` using the remaining elements in the list starting from index `i`. At each step:\n   - If the target becomes 0, it means we\'ve found a valid subsequence, and we return the length of that subsequence (0 in this base case).\n   - If we reach the end of the list (`i == arr.size()`) and the target is not zero, return an invalid result (`-(arr.size() + 1)`), which serves as a marker for an impossible subset.\n2. **Recursive Choices**:\n   - **Skip the current element**: We explore the possibility of not including the current element and move to the next element.\n   - **Include the current element**: If the current element can be part of the subsequence (i.e., `target - arr.get(i) >= 0`), we include it and reduce the target by its value. Add 1 to the length because we are including this element.\n3. **Memoization**: Use a 2D array `dp` where `dp[i][target]` stores the result for index `i` and the current target to avoid recomputation.\n4. **Result**: The final result is stored in `dp[0][target]`, representing the longest subsequence starting from the beginning and summing to the target. If no valid subsequence is found, return `-1`.\n\n### Complexity\n\n- **Time complexity**:  \n  The time complexity is `O(n * target)`, where `n` is the size of the array and `target` is the target sum. This is because each recursive call depends on two factors (the current index and the remaining target), and memoization ensures that each state is computed only once.\n\n- **Space complexity**:  \n  The space complexity is also `O(n * target)` due to the 2D DP array `dp` of size `n x (target + 1)` used for memoization.\n\n### Code\n\n```java\nclass Solution {\n    public static int subsetSum(List<Integer> arr, int i, int target, int[][] dp) {\n        // Base case: if we have gone through all elements\n        if (i == arr.size()) {\n            if (target == 0) return 0; // A valid subset has been found\n            return -(arr.size() + 1); // No valid subset, return a negative value\n        }\n\n        // If already computed, return the stored result\n        if (dp[i][target] != -1) {\n            return dp[i][target];\n        }\n\n        // Skip the current element\n        int skip = subsetSum(arr, i + 1, target, dp);\n        int ans = skip; // Set answer to skip by default\n\n        // Include the current element if the target allows\n        if (target - arr.get(i) >= 0) {\n            int pair = 1 + subsetSum(arr, i + 1, target - arr.get(i), dp); // Add 1 to the length\n            ans = Math.max(skip, pair); // Take the maximum of skip and pair\n        }\n\n        // Store the result in dp table\n        return dp[i][target] = ans;\n    }\n\n    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {\n        int[][] dp = new int[nums.size()][target + 1];\n\n        // Initialize dp array to -1 (meaning no solution computed yet)\n        for (int i = 0; i < nums.size(); i++) {\n            for (int j = 0; j <= target; j++) {\n                dp[i][j] = -1;\n            }\n        }\n\n        // Call the recursive function starting from index 0\n        int ans = subsetSum(nums, 0, target, dp);\n\n        // If no valid subsequence found, return -1\n        return ans < 0 ? -1 : ans;\n    }\n}\n```\n\n---\n\nThis solution efficiently finds the length of the longest subsequence that sums to a given target by combining recursion and memoization.
['Java']