🔥🔥 3-D Dynamic Programming Solution 🔥🔥
Intuition\nExplore all sub sequencs\nKeep track of min and max element in subsequence\n\n\n# Approach\nBy the way this will give TLE \u203C\n\nAt each index mak
# Intuition\nExplore all sub sequencs\nKeep track of min and max element in subsequence\n\n\n# Approach\nBy the way this will give TLE \u203C\n\nAt each index make 2 calls\n  1 for pick the element into subsequence\n  2 for not pick the element into subsequence\n\nreturn all the cases where minimum and maximum element has sum not greater than target\n\nthis question has 3-d dp approach\n\n\nAlso at the begining of code I put up 2 elements in nums\n1e9, -1e9 so that if the subset is empty then minimum element is 1e9 and maximum will be -1e9; and hence in base case we have terms like ind==nums.size()-2 (we substract 2 because of the 2 value we put in nums).\n\n# Complexity\n- Time complexity:\no(nxnxn)\n\n- Space complexity:\no(nxnxn)\n\n# Code\n```\nclass Solution {\npublic:\nint mod=1000000007;\n    long long int sol(vector<int>& nums, int target,int ind,int maxi,int mini,vector<vector<vector<long long int>>>&dp)\n    {\n\n          //// base cases\n        if(ind>nums.size()-2 )\n        return 0;\n\n        // cout<<ind<<endl;\n        \n        if(nums[maxi]+nums[mini]<=target && nums[maxi]!=-1e9 && ind==nums.size()-2)\n        return 1;\n        else if(ind==nums.size()-1)\n        return 0;\n\n        \n        if(dp[ind][maxi][mini]!=-1)\n        return dp[ind][maxi][mini];\n\n\n        /////pick,not pick\n        long long int notpick=sol(nums,target,ind+1,maxi,mini,dp)%mod;\n\n        ///// update min and max values\n        maxi=nums[maxi]>nums[ind]?maxi:ind;\n        mini=nums[mini]<nums[ind]?mini:ind;\n        long long int pick=sol(nums,target,ind+1,maxi,mini,dp)%mod;\n\n        return dp[ind][maxi][mini]= pick+notpick%mod;\n\n    }\n\n    int numSubseq(vector<int>& nums, int target) {\n        int n=nums.size();\n        nums.push_back(-1e9);\n        nums.push_back(1e9);\n        vector<vector<vector<long long int>>>dp(n+3,vector<vector<long long int>>(n+3,vector<long long int>(n+3,-1)));\n        return sol(nums,target,0,n,n+1,dp)%mod;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']