All Approaches : Recursive | Tabulation | Space Optimization 🚀💡
Intuition\n Describe your first thoughts on how to solve this problem. \nThe task is to find the longest subsequence from a list of integers whose sum equals a 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe task is to find the longest subsequence from a list of integers whose sum equals a given target. For each element, we have two choices:\n\nInclude the element if its value is less than or equal to the remaining target.\nExclude the element and move to the next one.\nThe goal is to maximize the length of the subsequence that sums to the target.\n\n<!-- Describe your approach to solving the problem. -->\n# Approach 1: Recursive + Memoization\nWe will solve the problem using recursion by trying two options at each step:\n\nNot Pick: Skip the current element and move to the next.\nPick: If the current element is less than or equal to the remaining target, include it and update the target.\n\nMemoization is used to store results of already computed subproblems in a dp array to avoid redundant calculations.\n\n# Complexity\n- Time complexity: O(n \xD7 target)\nEach subproblem is solved at most once, and there are n * target subproblems.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n \xD7 target)\nThis includes the space for the dp array and the recursion stack.\n\n# Code\n```java []\nclass Solution {\n    int dp[][];\n    public int solve(int idx, int n, List<Integer> nums, int target){\n        if (idx == n) {\n            return target == 0 ? 0 : -(int)1e8;\n        } else if (dp[idx][target] != -1) {\n            return dp[idx][target];\n        }\n\n        int notPick = solve(idx+1, n, nums, target);\n        int pick = -(int)1e8;\n        if (nums.get(idx) <= target) {\n            pick = 1 + solve(idx+1, n, nums, target - nums.get(idx));\n        }\n\n        return dp[idx][target] = Math.max(pick, notPick);\n    }\n\n    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {\n        int n = nums.size();\n        dp = new int[n+1][target+1];\n        for (int[] row : dp) {\n            Arrays.fill(row, -1);\n        }\n        int ans = solve(0, n, nums, target);\n        return ans <= 0 ? -1 : ans;\n    }\n}\n```\n\n# Approach 2: Tabulation\nInstead of using recursion, we can use an iterative method to fill a 2D dp table. The value dp[i][j] will represent the maximum length of a subsequence that can form a sum j using the first i elements.\n\n# Complexity\n- Time complexity: O(n \xD7 target)\nWe iterate through all elements (n) and for each element, we compute possible subsequences for all sums up to the target.\n\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n \xD7 target)\nWe use a 2D table to store results for each combination of elements and target values.\n\n# Code\n```java []\nclass Solution {\n    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {\n        int n = nums.size();\n        int dp[][] = new int[n+1][target+1];\n\n        for (int j = 1; j <= target; j++) {\n            dp[0][j] = -(int)1e8;\n        }\n\n        for (int i = 1; i <= n; i++) {\n            for (int j = 1; j <= target; j++) {\n                int notPick = dp[i-1][j];\n                int pick = -(int)1e8;\n                if (nums.get(i-1) <= j) {\n                    pick = 1 + dp[i-1][j - nums.get(i-1)];\n                }\n                dp[i][j] = Math.max(pick, notPick);\n            }\n        }\n        return dp[n][target] <= 0 ? -1 : dp[n][target];\n    }\n}\n```\n\n# Approach 3: Space Optimization\nWe can optimize the tabulation approach by reducing space complexity. Instead of using a 2D dp table, we use two arrays: prev (representing the results from the previous row) and curr (representing the results from the current row). After processing each row, we set prev to curr and repeat the process.\n\n# Complexity\n- Time complexity: O(n \xD7 target)\nTime complexity remains the same since we still iterate over all elements and target values.\n\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(2 * target)\nInstead of using a 2D array, we now only need two arrays of size target + 1, reducing the space complexity to linear in terms of the target.\n\n# Code\n```java []\nclass Solution {\n    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {\n        int n = nums.size();\n        int prev[] = new int[target+1];\n        for (int j = 1; j <= target; j++) {\n            prev[j] = -(int)1e8;\n        }\n\n        for (int i = 1; i <= n; i++) {\n            int curr[] = new int[target+1];\n            for (int j = 1; j <= target; j++) {\n                int notPick = prev[j];\n                int pick = -(int)1e8;\n                if (nums.get(i-1) <= j) {\n                    pick = 1 + prev[j - nums.get(i-1)];\n                }\n                curr[j] = Math.max(pick, notPick);\n            }\n            prev = curr.clone();\n        }\n        return prev[target] <= 0 ? -1 : prev[target];\n    }\n}\n```\n\n\n**If you found this helpful, please give it an upvote! \uD83D\uDC4D\nFeel free to drop a comment if you have any queries! \uD83D\uDCAC\uD83D\uDE0A**
['Array', 'Dynamic Programming', 'Recursion', 'Java']