SIMPLE SOLUTION EXPLAINED IN DETAIL || TIME O(M * POW(2,N))
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThe problem is a bit hard to crack.Let me tell you how to solve this problem in compl
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe problem is a bit hard to crack.Let me tell you how to solve this problem in complete detail\n\nlet the \n\nreq_skills = ["algorithms","math","java","reactjs","csharp","aws"]\n\n**Now we know there are total 6 skills so let us take 6 bits .**\n\nHow we will reprsent it , **it will be represented by "000000"**\n\nNow, Let us say algo represnts 0th bit so let us convert the 0th bit to 1 , so after conversion our bit looks **like this "000001"**\n\nLet math be the 1st bit , so now convert the 1\'st bit so it will look like **"000011"**\n\nLet java be 2nd bit, so convert it also, so bit looks like **"000111"**\n\nLet react be 3rd bit , so bit looks like **"001111"**\n\nLet csharp be 4th bit, so bit looks like **"011111"**\n\nLet aws be 5th bit, so bit looks like **"111111"**\n\n\nNow Let the people array be \n\npeople = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]\n\nNow for index no 0  => we  have 3 skills , **algo, math and java** \n\nnow we knew that **algo is our 0th bit, math is 1st bit and java is 2nd bit**, so it means that we turn this bits on , the reprenstaion of this index will be **"000111"**\n\nNow for index 1 => we have **algo(0th bit), math(1st bit),react(3rd bit)**\nso the represenation will be **"001011"**\n\nNow for index 2 => we have **java(2nd bit), csharp(4th bit), aws(5th bit)** so the represnetaion will be like **"110100"**\n\nNow for index 3 => we have **react(3rd bit), csharp(4th bit)**, so the representation will be **("011000")**\n\nNow for index 4=> the represnetaion will be **"010010"**\n\nFor index 5 => it will be **"100100"**\n\nNow the people array looks like this ["000111","001011","110100","011000","010010","100100"]\n\nNow the question becomes something like this \n\n**Select few elements from this people array to make the total sum as "111111" and the elemets selected should be the minimum**\n\n\nNow, tell me one thing , here we have multiple options\n\nwe can select 0 or we do not select it\nwe can select 1 or we do not select it\nwe can select 2 or we do not select it..\n\nso it means **we need to try all the cases and for such a thing** , **we will take help of recursion**\n\nWhat will be the base case \n\nlet us say initially our sum is 0, and we add few elements from the people\'s array, and if our **sum becomes "111111"**, then we will **return 0** , because that is a possible ans\n\nIf, while traversing the people\'s array we reach the end of people\'s array , **which means i==people.size()**, it means we were not able to find our ans so we **return a really large value**\n\n**Why did we return a large value,**\n\nIt is simple, we need to get the minimum value and we know that if i reaches people.size(), **Then definitley that won\'t be our ans**, so we return the worst value possible.\n\nNow , In our recursion , there will be 2 conditions \n\n**1) We can select that index from our people\'s array**\n\n**2) We won\'t select it and move on**\n\nIf we select it, it means **we are increasing the count of element by 1 and the sum will also become sum+=people[i]**\n\nwe just need to return the min of the both cases\n\n**BUT BUT BUT, OUR QUESTION ASKED US TO RETURN THE INDEX WHICH WE SELECTED, SO HOW DO WE DO THAT**\n\nWe know that we will be returning the min of our 2 cases,\n\nNow in one case , **we are selecting and element => let us say this is case "A"**\n\nNow in second case, **we are just moving on to the next element, Let\'s say this is case "B"**\n\n**IF(A<B) => IT WILL STATE THAT THE INDEX I WHICH WE SELECTED WAS USEFUL, SO WE WILL JUST MARK THAT INDEX DOWN, HOW DO WE MARK IT**\n\nWE WILL JUST MAKE ANOTHER 2-D ARRAY FOR IT, SAYING THAT \n\n**CHOICE[INDEX][SUM_WHICH_IS_GOING_ON]=1**\n\nNow, when we return to our main function , **we will be just iterating in the array and finding all such elements where choice[i][sum]==1 and push that index in our result..**\n\n\n***IK THIS PROBLEM IS DIFFICULT, IF YOU STILL FIND DIFFICULT, TAKE A COPY PEN (SOLVE THIS QUESTION UNTIL YOU DIE :) )***\n\n\nMEMOIZATION\n\nWE KNOW THAT ONLY TWO THINGS ARE CHANGING , \n\n1) FIRST THE INDEX (I)\n2) SECOND THE SUM\n\nSO JUST MAKE A 2-D DP ARRAY AND STORE YOUR RESULTS IN **DP[I][SUM]**\n\n**TRICK**\n\n***WHENEVER YOU SEE SUCH QUESTION, JUST CHECK WHAT ARE THE ONLY PARAMETERS CHANGING , HERE ONLY 2 WERE CHANGING, SO THAT IS WHY WE APPLIED MEMOIZATION HERE*** \n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nWE WILL BE JUST ITERATING THE WHOLE PEOPLE\'S SIZE AND FOR EVERY INDEX WE WILL BE CALCULATING DIFFERENT SUM\'S , \n\nLET\'S SAY PEOPLE SIZE = M AND FOR SUM,\n\nWE KNOW THAT IF THE REQ_SKILLS.SIZE = 6, THEN IT MEANS THE SUM WILL BE FROM 0 TO "111111"\n\nSO IT MEANS THAT \n\n**(M * POW(2,N))**\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nWE ARE STORING IN A 2D - DP-ARRAY, SO **O(M * POW(2,N))** \n\n# Code\n```\nclass Solution {\npublic:\n\nvector<int>solution;\n    int  solve(int mask,vector<int>&lmask,int i,int op,vector<vector<int>>&dp,vector<vector<int>>&choice)\n    {\n\n        if(op==mask)\n        {\n            return 0;\n        }\n\n        if(i==lmask.size())\n        {\n            \n            return 10000;\n        }\n\n        if(dp[i][op]!=-1)\n        {\n            return dp[i][op];\n        }\n\n\n        int a = solve(mask,lmask,i+1,op,dp,choice);\n\n    \n        int b = 1+solve(mask,lmask,i+1,op|lmask[i],dp,choice);\n        \n\n        if(b<a)\n        {\n            choice[i][op] = 1;\n        }\n\n        dp[i][op] = min(a,b);\n\n        return min(a,b);\n    }\n\n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n        \n        unordered_map<string,int>jd;\n\n        int n = req_skills.size();\n        int mask = (1<<n)-1;\n\n        int count  = 0;\n\n        vector<vector<int>>dp(people.size(),vector<int>(pow(2,n),-1));\n\n        vector<vector<int>>choice(people.size(),vector<int>(pow(2,n),-1));\n    \n        vector<int>lmask;\n        for(int i=0; i<req_skills.size(); i++)\n        {\n            jd[req_skills[i]] = count;\n            count++;\n        }\n\n        for(int i=0; i<people.size(); i++)\n        {\n            int a = 0;\n\n            for(int j=0; j<people[i].size(); j++)\n            {\n\n                int x = jd[people[i][j]];\n                a = (a | (1<<x));\n\n            }\n            lmask.push_back(a);\n        }\n        int op =0;\n        solve(mask,lmask,0,op,dp,choice);\n\n      int x = 0;\n    vector<int>res;\n\n  for(int i=0; i<people.size(); i++)\n  {\n\n      if(choice[i][x]==1)\n      {\n          res.push_back(i);\n          x|=lmask[i];\n      }\n\n      if(x==mask)\n      {\n          return res;\n      }\n\n  }\n\n  return res;\n\n    }\n};\n```\n\n**TIME FOR A MEME NOW** \n\n![IMG-20230716-WA0033.jpg](https://assets.leetcode.com/users/images/d282c973-c650-4709-baf3-f064af509a0d_1689521305.621808.jpeg)\n\n**IF YOU LIKE MY SOLUTION , PLEASE UPVOTE....**\n
['Array', 'Dynamic Programming', 'Bit Manipulation', 'Bitmask', 'C++']