C++ Solution | DP + BitMask | Explained | All 3 approaches i.e. Recursion, Memoization and DP
Intuition\n### Recursive Intuition:\nTake or leave the current person, continue till you get all the required skills\n### Memoization Intuition:\nJust store the
# Intuition\n### Recursive Intuition:\nTake or leave the current person, continue till you get all the required skills\n### Memoization Intuition:\nJust store the result of the recursive solution in terms of current mask and index\n### Dynamic Programming Intuition:\nCalculate each person\'s skill value and use find the number of people for each possible combination\n\n\n# Masking\nInstead of using strings for comparison, we use bit position to represent the skill\nIf the ith position in a combination is set, that means that the person has that skill else he/she doesn\'t have that skill\nTherefore, we assign each skill an index position determing that if that bit is set, the skill is present and vice-versa\n\n# Recursive Approach\nIn the recursive approach, we use the same concept as 0-1 Knapsack Problem\nWe either include the current person in our list, you we don\'t \nHere I have used bitset, just to show each individual bit.\nSame can the done using an integer and a left shift operator\n\n# Recursive Code\n```\n \nclass Solution {\npublic:\n    void helper(bitset<16> skill_set ,  vector<bitset<16>> &people, vector<int> &ans, int skills, vector<int>& t_ans, int curr_index, int size){\n        if(ans.size() > 0 && t_ans.size() > ans.size()){\n            // if we have an answer already and the new answer that we may get will be greater in size than the previous one\n            // Therefore, we don\'t need to proceed forward\n            // Just an optimization, the code will run fine without this also\n            return;\n        }\n        if(skill_set.count() == skills ){\n            // if we get the number of skills we want\n            if(t_ans.size() < ans.size() || ans.size() == 0){\n                // If we get the number of skills using lesser number of people\n                ans = t_ans;   \n            }\n            return;\n        }\n\n        if(curr_index == size){\n            // Base condition\n            return;\n        }\n\n        bitset p = people[curr_index];\n        // The skills that the current person has\n        if(p.count() > 0){\n            // Another optimization statement \n            // we would only want to a person, if he/she has some skill\n            bitset<16> n(skill_set);\n            n = n | p;\n            t_ans.push_back(curr_index);\n            // including the current person\n            helper(n , people, ans, skills, t_ans, curr_index+1,size);\n            t_ans.pop_back();\n        }\n\n        // not including the current person\n        helper(skill_set , people, ans, skills, t_ans, curr_index+1,size);\n    }\n\n\n\n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n\n        int skills = req_skills.size();\n        int size = people.size();\n        bitset<16> skill_set;\n        // mapping all the skills to a number i.e. bit position\n        unordered_map<string, int> mapping;\n        for(int i = 0; i<skills; i++){\n            mapping[req_skills[i]] = i;\n        }   \n\n        // Vector of bitsets containing all the skill sets of the people\n        vector<bitset<16>> people_skills;\n        for(auto i: p){\n            bitset<16> b;\n            for(auto j : i){\n                int a = mapping[j];\n                b.set(a);\n            }\n            people_skills.push_back(b);\n        }\n\n        vector<int> ans;\n        vector<int> t_ans;\n        // Calling recursion\n        helper(skill_set, people, ans, skills,t_ans,0, size);\n        return ans;\n    }\n};\n```\n\n\n\n\n# Memoization Approach\nIn the Memoization approach, we store the result of the recursive calls, so that we don\'t have to do the same work again\nIn this, we make two vectors one is DP, that will store the answer size and one will be choice, that will store whether the ith person is included or not\nWe return the total number of people that we have included in this approach\nIn this approach, I have used the whole number instead of bitset.\n\n# Memoization Code\n```\nclass Solution {\npublic:\n    int solve(vector<int>&skill_person,int curr_mask, int curr_index,\n            vector<vector<int>> &dp, vector<vector<int>> &choice, \n            int &no_people, int &req_mask){\n        if(curr_mask == req_mask){\n            // We got all the skills\n            // Therefore, we return 0\n            return 0;\n        }\n        if(curr_index == no_people){\n            // We are at the end of the list\n            // Cannot include any one now\n            // Need to somehow reject this case\n            // hence return a large number\n            return 10000;\n        }\n        if(dp[curr_mask][curr_index] != -1){\n            // if we have calculated the result before\n            return dp[curr_mask][curr_index];\n        }\n        // include the current person in our list and proceed\n        int including = solve(skill_person, curr_mask|skill_person[curr_index], curr_index+1, dp,choice, no_people, req_mask) + 1;\n        // don\'t include the current person in our list and then proceed\n        int not_including = solve(skill_person, curr_mask, curr_index+1, dp,choice, no_people, req_mask);\n\n        if(including< not_including){\n            // If we can get a lesser answer by including the person\n            // So we include this person\n            // Hence set the choice of this case as one which means that for the current mask and at the current index, this person is useful for us.\n            choice[curr_mask][curr_index] = 1;\n        }\n        // Storing the answer\n        dp[curr_mask][curr_index] = min(including, not_including);\n        return dp[curr_mask][curr_index];\n    }\n\n    vector<int> smallestSufficientTeam(vector<string>& req_skills,\n                vector<vector<string>>& people) {\n\n        int skills = req_skills.size();\n        int no_people = people.size();\n        int possible = pow(2, skills);\n\n        // mapping all the skills to a number i.e. bit positions\n        unordered_map<string, int> mapping;\n        for(int i = 0; i<skills; i++){\n            mapping[req_skills[i]] = i;\n        }\n\n        // Vector of integers containing the value of each person\'s skill value\n        vector<int> skill_person(no_people);\n        for(int i = 0; i<no_people; i++){\n            int size = people[i].size();\n            int val = 0;\n            for(int j = 0; j<size; j++){\n                int index = mapping[people[i][j]];\n                val = val | (1<<index);\n            }\n            skill_person[i] = val;\n        }\n\n        // Required mask i.e. all the required skills are fulfilled\n        int req_mask = (1<<skills)-1;\n        vector<vector<int>> dp(possible,vector<int>(no_people+1 ,-1));\n        vector<vector<int>> choice(possible,vector<int>(no_people+1 ,-1));\n\n        solve(skill_person,0, 0, dp, choice, no_people, req_mask);\n\n        vector<int> ans;\n        int mask = 0;\n        for(int i = 0; i<no_people; i++){\n            if(choice[mask][i] == 1){\n                // If the person was included at that particular point, we need to include him in the current answer\n                ans.push_back(i);\n                // Changing the mask including the current person skills as well\n                mask = mask| skill_person[i];\n            }\n            // As soon as we get the required mask, we break\n            if(mask == req_mask){\n                break;\n            }\n        }\n        return ans;\n    }\n}\n\n```\n\n# Dynamic Programming Approach\nIn the Dynamic Programming approach, we make the answer from bottom to top \nIn this approach also, we calculate the skill value of each person, after giving each skill a bit position.\n\n\n\n# Dynamic Programming Code\n```\nclass Solution {\npublic:\n    vector<int> smallestSufficientTeam(vector<string>& req_skills,\n            vector<vector<string>>& people) {\n        int skills = req_skills.size();\n        int no_people = people.size();\n        int possible = pow(2, skills);\n        \n        unordered_map<string, int> mapping;\n        for(int i = 0; i<skills; i++){\n            mapping[req_skills[i]] = i;\n        }\n\n\n        unordered_map<int, vector<int>> dp;\n        dp.reserve(1 << skills);\n        dp[0] = {};\n\n        for(int i = 0; i<no_people; i++){\n            int size = people[i].size();\n            int val = 0;\n            // calculating the skill value of each person\n            for(int j = 0; j<size; j++){\n                int index = mapping[people[i][j]];\n                val = val | (1<<index);\n            }\n\n            // Iterating over the all possible combinations possible \n            // and checking if after including this person, we can \n            // get to a skill value that has a higher person count \n            // than that if we include this person\n            // Or if we can get a new value that has no person \n            for (auto it = dp.begin(); it != dp.end(); ++it) {\n                int comb = it->first | val;\n                if (dp.find(comb) == dp.end() || \n                    dp[comb].size() > 1 + dp[it->first].size()){\n                        dp[comb] = it->second;\n                        dp[comb].push_back(i);\n                }\n            }\n\n            // this can also be used \n            // for (auto it: dp) {\n            //     int comb = it.first | val;\n            //     if (dp.find(comb) == dp.end() || \n            //         dp[comb].size() > 1 + dp[it.first].size()){\n            //             dp[comb] = it.second;\n            //             dp[comb].push_back(i);\n            //     }\n            // }\n            \n        }\n\n        // returning the people including at the last position \n        // i.e. when all the skill bits are set\n        return dp[possible-1];\n    }\n}\n```\n
['Dynamic Programming', 'Bit Manipulation', 'Recursion', 'Memoization', 'C++']