✅Easy C++ Code with Detailed Intuition+Approach | DP in interviews | Why DP? Bitmask?
Intuition\n Describe your first thoughts on how to solve this problem. \nPrerequisites - basic understanding of DP problems and use of bit-masking\nThis kind of
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nPrerequisites - basic understanding of DP problems and use of bit-masking\nThis kind of problem can be very difficult in interviews if you have not solved it earlier. However, when we go through the problem statement once we can see that we need to find **minimum team size** from the given array of people so that we are able to fulfill the required skills. It is the case of take or not-take appoach using DP.\n\nBrute force recursion with meomorization (keeping track of skills covered so far will lead to meomory limit exceeded error).\nNow here bit masking comes into the play to further optimise the space. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nRole of Bitmask - Now we will map every required skill to an index(just a representation). \nSuppose we have 5 required skills so think of intial binary representation as 00000\n\nNow using the index of the required skills which we did above set the corresponding index to 1 using a loop which will be ultimately lead to the "required skill score" as "11111".\n\nSince we converted the required skill into a score, so we should also convert the skills of people into their correspoding scores.\nUsing the index of the skill of the people we set the corresponding index to 1 using a loop. The skill score calculated will be stored in "people_skill_scores" array.\n\nWe are ready to apply dp on the calculated array. We will pass index of people, "people_skill_scores" array, current score, required score, current team storing index of selected people, required team to store the final team of minimum size.\n\nI will now explain the recursion function(refer to code as well side by side):\n//Base Case\nAs soon as we get the current score equals required score we can check if the it\'s the first time we got the answer or the current team size if smaller than the team we got in the past and we will update the answer.\n\nOther condition we need to check if we reached the end of the array.\n\n//Recusion\nCase1: Skip the current people\nCase2: Take the current people\n\nFor case2: I have done little optimisation,i.e, we only take the people if he/she is adding some skills to the lot or not. If we have got his/her skills from the past then it is not required to include him in the team.\nHere in the current team array we store the position of the people.\n\n\n//Meomorization\nWe need to keep track of two variable the postion of people array and current score. The current team array and required team array are just to store the answer.\n\nIn dp array we will store the team size because we are minimising that only. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nN = size of people array\nk = size of required skills array\n\nO(N*pow(k,2))\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N*pow(k,2))\n# Code\n```\nclass Solution {\n    unordered_map<string,int> skill_idx;\n    void solve(vector<int>& people_skill_scores, int pos, int req_score, int curr_score, vector<int>& curr_team, vector<int>& req_team, vector<vector<int>>& dp){\n        //base case\n        if(curr_score == req_score){\n            if(req_team.size() == 0 || curr_team.size() < req_team.size()){\n                req_team = curr_team;\n            }\n            return;\n        }\n        if(pos == people_skill_scores.size()){\n            return;\n        }\n\n        if(dp[pos][curr_score] != -1){\n            //current team size is greater than existing team size so return\n            if(dp[pos][curr_score] <= curr_team.size()){\n                return;\n            }\n        }\n        \n        //skip\n        solve(people_skill_scores,pos+1,req_score,curr_score,curr_team,req_team,dp);\n        \n        //take\n        //Because a person\'s skill set may not be contributing. So we won\'t take them\n        if(curr_score | people_skill_scores[pos] != curr_score){\n            curr_score = curr_score | people_skill_scores[pos];\n            curr_team.push_back(pos);\n            solve(people_skill_scores,pos+1,req_score,curr_score,curr_team,req_team,dp);\n            curr_team.pop_back();\n            dp[pos][curr_score] = curr_team.size();\n        }\n    }\npublic:\n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n        //mapping skill to index and calculation of required skill score\n        int req_score = 0;\n        for(int i = 0; i < req_skills.size(); i++){\n            skill_idx[req_skills[i]] = i;\n            int mask = (1 << i);\n            req_score = req_score | mask;\n        }\n\n        //calculation of people\'s skill score\n        vector<int> people_skill_scores;\n        for(auto people_skills: people){\n            int skill_score = 0;\n            for(auto skill: people_skills){\n                int idx = skill_idx[skill];\n                int mask = (1 << idx);\n                skill_score = skill_score | mask;\n            }   \n            people_skill_scores.push_back(skill_score);\n        }\n\n        vector<int> req_team; //to store final ans\n        vector<int> curr_team; //work as temporary array \n        vector<vector<int>> dp(people.size(), vector<int>(req_score+1,-1));\n        solve(people_skill_scores,0,req_score,0,curr_team,req_team,dp);\n        return req_team;\n    }\n};\n```
['Dynamic Programming', 'Bit Manipulation', 'Memoization', 'Bitmask', 'C++']