Dp solution or Greedy Solution
Intuition\nbasice Intuition for this Question is we have just see we can take that number or not.\n# Approach\nThis Question is done by two approch one is greed
# Intuition\nbasice Intuition for this Question is we have just see we can take that number or not.\n# Approach\nThis Question is done by two approch one is greedy and second one is Dynamic Programming.\n1) In greedy first sort nums array because we have to find max length so when we sort whole array in ascending order we can take as possible as minimum number and we can increase array size so with this approch we can get max length.\n2) In dp first sort nums array and think about recurence relation like at each number we have to possibility either take or not take and at the end we can return max and you can see overlapping subproblem so we can use dp.\n\n# Complexity\n- Time complexity:\n1) Greedy O(N^2)\n2) dp O(N^2)\n- Space complexity:\n1) O(1)\n2) O(N)\n\n# Code\n```\n//dp approch\nclass Solution {\npublic:\nint findmaxlength(vector<int> &dp,int ind,int sum,vector<int> &num)\n{\n\t//base condition\n\tif(ind>=num.size())return 0;\n\tif(dp[ind]!=-1)return dp[ind];\n\tint takel=INT_MIN,notakel=INT_MIN;\n\tif(sum-num[ind]>=0)\n\t{\n\t\tsum-=num[ind];\n\t\ttakel=1+findmaxlength(dp,ind+1,sum,num);\n\t\tsum+=num[ind];\n\n\n\t}\n\tnotakel=0+findmaxlength(dp,ind+1,sum,num);\n\t return dp[ind]=max(notakel,takel);\n}\n    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {\n        int n=nums.size();\n        int m=queries.size();\n        vector<int> ans;\n\tsort(nums.begin(),nums.end());\n\tfor(int i=0;i<m;i++)\n\t{\n\t\tvector<int> dp(n,-1);\n\t\tans.push_back(findmaxlength(dp,0,queries[i],nums));\n\t}\n    return ans;\n        \n    }\n};\n```\n# Code\n```\n//greedy approch\nclass Solution {\npublic:\n    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {\n        int n=nums.size();\n        int m=queries.size();\n        vector<int> ans;\n        sort(nums.begin(),nums.end());\n        for(int i=0;i<queries.size();i++)\n        {\n            int sum=queries[i];\n            int count=0;\n            for(int j=0;j<nums.size();j++)\n            {\n                if(sum-nums[j]>=0)\n                {\n                    count++;\n                    sum-=nums[j];\n                }\n            }\n            ans.push_back(count);\n        }\n        return ans;\n        \n    }\n};\n\n
['Dynamic Programming', 'Greedy', 'C++']