Step by Step explained with intuition beginner friendly  C++(recursion +memoization)
Intuition\nUnderstanding the Problem:\nAt its core, the problem is asking us to find the longest subsequence that sums up to the target. This means, for every e
# Intuition\nUnderstanding the Problem:\nAt its core, the problem is asking us to find the longest subsequence that sums up to the target. This means, for every element in the array, we have two choices:\n\nInclude the element in the subsequence.\nExclude the element from the subsequence.\n\n#### Brainstorming the Approach:\nIf we go with the naive way, which is trying out all the possible combinations, the time complexity will be exponential (specifically \nO(2^n) where n is the length of the array). This is clearly inefficient for larger arrays.\n\nHowever, a key insight here is the repetitive nature of the problem. For instance, after choosing to include/exclude a specific element, we\'re essentially solving a smaller version of the same problem for the remaining part of the array with an updated target. This repetitive substructure hints at the applicability of dynamic programming.\n\nFormulating the Recursive Function:\nLet\'s define a function f(i, k) that represents the length of the longest subsequence starting from the i-th element of the array with a sum of k. Now, to compute this, we can either:\n\nInclude the i-th element, in which case our new target becomes k - ar[i], and our subsequence length increases by 1.\nExclude the i-th element, where our target remains k and the subsequence length remains unchanged.\nSo, f(i, k) = max(f(i+1, k-ar[i]) + 1, f(i+1, k)).\n\nDynamic Programming (Memoization):\nThe above recursive relation will still lead to an exponential time solution due to overlapping subproblems. For instance, f(2, 50) might be computed multiple times through different paths.\n\nThis is where dynamic programming shines. By caching the results of subproblems in the dp table, we avoid redundant calculations. Now, before diving into our recursive calculations, we check if the result for this state (i, k) is already computed. If yes, we return the cached result. If not, we compute and store it.\n\nFinal Thoughts:\nThe dynamic programming approach ensures that each subproblem is solved only once, reducing the time complexity from exponential to polynomial (specifically O(n\xD7target), where n is the length of the array).\n\nIn summary, by recognizing the problem\'s choice-based and repetitive structure, we employed a dynamic programming approach to efficiently find the solution.\n\n# step by step explanation\nInitialization:\n\nA 2D array dp is used to store the results of subproblems. The dimensions are 1001x1001 assuming that\'s the maximum constraints for the problem.\nThe function f(int i, vector<int>& ar, int k) represents the longest subsequence length starting from index i and having a sum of k.\n\n### Base Cases:\nIf k < 0, it means that the target cannot be achieved by including any further elements, so we return a very negative value (using INT_MIN) to indicate the impossibility.\nIf i reaches the size of the array:\nIf k becomes 0, it means the target has been achieved, so we return 0.\nOtherwise, we return INT_MIN to indicate the impossibility.\n\n### Memoization:\nIf the subproblem has been solved before (i.e., dp[i][k] is not -1), then return the cached result.\n\n### Recursive Case:\nFor every element, we have two choices:\nInclude the element in the subsequence, so we reduce the target by ar[i] and add 1 to the result.\nExclude the element from the subsequence and keep the target unchanged.\nWe want the maximum length, so we take the maximum of these two choices.\n\n### Main Function (lengthOfLongestSubsequence):\nInitialize the dp array with -1.\nCall the recursive function f(0, ar, target) to get the result. If the result is negative, return -1, otherwise return the result.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int dp[1001][1001];\n    int f(int i,vector<int>& ar, int k){\n        if(k<0) return INT_MIN;\n        if(i==ar.size()){\n            if(k==0) return 0;\n            else return INT_MIN;\n        }\n        if(dp[i][k]!=-1) return dp[i][k];\n        return dp[i][k]=max(f(i+1,ar,k-ar[i])+1,f(i+1,ar,k));\n    }\n    \n    int lengthOfLongestSubsequence(vector<int>& ar, int target) {\n       // int n=nums.size();\n        memset(dp,-1,sizeof(dp));\n        if(f(0,ar,target)<0) return -1;\n        return f(0,ar,target);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']