O( n^2 )✅ | Python (Step by step explanation)✅
Intuition\nThe code solves a problem related to finding the length of the longest subsequence of a given vector nums whose sum is equal to the target. The code 
# Intuition\nThe code solves a problem related to finding the length of the longest subsequence of a given vector `nums` whose sum is equal to the `target`. The code uses a dynamic programming approach to achieve this.\n\n# Approach\n1. The knapsack function is a recursive function that takes three parameters: i (the current index in the nums array), nums (the input array), and target (the remaining target value).\n\n2. If target becomes zero, it means you have found a valid subsequence, so it returns 0.\n\n3. If target becomes negative or i goes beyond the size of the nums array, it returns negative infinity (INT_MIN), indicating that this branch of the recursion is not valid.\n\n4. The code uses memoization with a 2D array dp to store intermediate results. If the result for the current i and target is already computed, it returns that value.\n\n5. It calculates two values:\n\n- take: Represents the length of the subsequence if the current element is included, and target is reduced by the value of nums[i].\n- leave: Represents the length of the subsequence if the current element is excluded.\n6. The maximum of take and leave is computed and stored in dp[i][target], which represents the maximum length of the subsequence starting from index i with the given target.\n\n7. The lengthOfLongestSubsequence function initializes the dp array with -1, calls the knapsack function from index 0 with the target value, and checks if the result is non-positive (indicating no valid subsequence) and returns -1. Otherwise, it returns the computed answer.\n\n# Complexity\n- Time complexity: O(N * T), where N is the length of the `nums` array, and T is the target sum. This is due to the number of unique subproblems computed in the dynamic programming approach.\n- Space complexity: O(1) because it uses a constant amount of space, primarily for the memoization table.\n\n\n\n# Code\n```\nclass Solution {\npublic:\n    int dp[1001][1001] ;\n    int knapsack(int i , vector<int>& nums , int target){\n        if(target==0){\n            return 0;\n        }\n        if(target < 0 || i >= nums.size()){\n            return INT_MIN;\n        }\n        if(dp[i][target] != -1){\n            return dp[i][target];\n        }\n\n        int take = 1 + knapsack(i+1 , nums ,target-nums[i]);\n        int leave = knapsack(i+1 , nums , target);\n        return dp[i][target] = max(take ,leave);\n    }\n\n    int lengthOfLongestSubsequence(vector<int>& nums, int target) {\n        memset(dp , -1 , sizeof(dp));\n        int ans = knapsack(0 , nums , target);\n        if(ans <= 0){\n            return -1;\n        }\n        return ans;  \n    }\n};\n```\n\n# Please upvote the solution if you understood it.\n![1_3vhNKl1AW3wdbkTshO9ryQ.jpg](https://assets.leetcode.com/users/images/d4803813-f733-4524-93db-c2567a021757_1698600692.7262573.jpeg)\n
['Dynamic Programming', 'Recursion', 'C++']