C++ Bitmasking solution with dp memory | 99% Time
Intuition\n Describe your first thoughts on how to solve this problem. \nThe core idea is to go by skill instead of by person; in other words, for each skill, y
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe core idea is to go by skill instead of by person; in other words, for each skill, you need to find someone to fit into that role. This means that you can just try putting people in the role and then figuring what other things they bring to the table.\n\nSince the amount of skills is so low (maximum of 16), we can map sets of skills to integers by having each bit place be a 1 if the skill exists, and a 0 if it does not. Then we can use the bitwise or ("|") in order to "add values to the set". \n\nFinally, if we go through the skills in order, then when we are looking at any given skill, we can just assume that all of the previous skills have people that fufill them in some way. Thus we only need to worry about the best possible future from the current starting point. This means that we can store the best possible path forward (based on what is already completed), and return it in order not to do repeated operations. They key is that we only care about WHAT future skills are completed, and not HOW they are completed. Thus, we can use the portion of the mask purtaining to the future bits as our key. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nI used recursion + back-tracking to help me go down all of the possible paths. I did this by starting with the index of the skill I need to fufill (pos), as well as a mask that ONLY contains information about the future positions (mask). Note that this means that the mask has less bits, depending on the position, with exactly (n - pos) bits (where n = number of skills). If we have tried to do this exact setup before (seenSkill), then we can just return whatever we found was most efficient. \n\nThen, I searched through my dictionary of people who have the corresponding skill (withSkill), and for each person, try to add their skills to the pool (peopleSkillMask), and recursively fufill find the best from the next unfinished skill. Notice that the best path from the next open spot may also think that the current person is the best way to fufill some other future skill, so only add it if not already in the set of best people. Then, choose the best possible future path, save it, and return it. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(mn^2)$$ because the lists that have to be copied, as well as there being possibly a lot of people specialized to a specific skill. However, I am not confident in this analysis, as there are things that could affect the time complexity such as people only ever showing up once in each branch of recursion, as it will skip over all occurances of the person, as well as under the hood implementations that could affect time complexity with regards to copying. If someone could do a deeper analysis, that would be great!\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is potentially massive, with $$O(n2^n)$$, but since n is consistently small, it is not as much of a problem.\n# Code\n```\nclass Solution {\npublic:\n    // Make sure not to add repeats in when pulling from a seen (as the seen may try to use it already)\n    bool inList(int item, vector<int> &list) {\n        for (int i : list)\n            if (item == i) \n                return true;\n        return false;\n    }\n    // Get next "0" in the mask (aka next missing skill) from the current mask to get the next place to go\n    int getNextZero(int mask) {\n        for (int i = 0; mask >= 0; i++, mask >>= 1) {\n            // cout << mask << endl;\n            if (mask % 2 == 0) return i;\n        }\n            \n        return 0;\n    }\n\n    // Assumes that skills 0...pos are dealt with, so we only care about the future\n    // The mask is the skills required AFTER the pos point (aka mask only has the amount of digits as there are skills left)\n    vector<int> dfs(int pos, int mask, \n        vector<int> &peopleSkillMask, vector<vector<int>> &withSkill, vector<unordered_map<int, vector<int>>> &seenSkill) {\n        \n        int n = withSkill.size();\n        // NOTE: The mask does not contain ANY INFORMATION on [0...pos), as we are just assuming they are 1s\n        \n        // For whatever reason, if tries to go to a skill further than possible, then it is a bad solution\n        if (pos > n) return vector<int>(n + 1, 0);\n        // If it used up all the skills, then we are good to go\n        if (pos == n or mask == (1 << (n - pos)) - 1) return {};\n\n        // If we have found an efficient solution to get the remaining skills, just use that\n        if (seenSkill[pos].count(mask) == 1) return seenSkill[pos][mask];\n        \n        vector<int> bestList(n + 1, 0);\n        for (int person : withSkill[pos]) { // For each candidate...\n            \n            // Mark this + future skills by trying to use the current candidate\n            int newMask = mask | (peopleSkillMask[person] >> (pos));\n            int next = getNextZero(newMask); // Then find the next unsused skill\n\n            // Go to the next unused skill (Note the newMask shift is to get rid of all the unecessary info between pos and the \n            // new skill position)\n            vector<int> list = dfs(pos + next, newMask >> next, peopleSkillMask, withSkill, seenSkill);\n\n            // Only add it if the most efficient path forward doesn\'t already use it\n            if (not inList(person, list))\n                list.push_back(person);\n            \n            // Only set the list if it uses less people\n            if (list.size() < bestList.size())\n                bestList = list;\n        }\n        // This is now the path with the future skills used that has the best path forward\n        seenSkill[pos][mask] = bestList;\n        return bestList;\n    }\n\n\n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n        int n = req_skills.size(), m = people.size();\n        // JUST FOR SET UP: Efficiently allows mapping from skill names to that actual index value\n        unordered_map<string, int> skillToIndex;\n        vector<bool> seenSkills(n, false);\n        for (int i = 0; i < n; i++) \n            skillToIndex[req_skills[i]] = i;\n\n        // Complete = 1...1 (n times), so if it is in the set, it is a one (this only works bc n is small)\n        int completeMask = (1 << n) - 1;\n        \n        // Stores the skills that a person has as a binary number (with a skill corresponding to a place)\n        vector<int> peopleSkillMask;\n        // Stores which people work based on skill (so we can search by skill and test adding the people)\n        vector<vector<int>> withSkill(n, vector<int>());\n        // Stores if we have seen the most optimal path moving forward from the current skill (ignoring previous skills)\n        vector<unordered_map<int, vector<int>>> seenSkill(n, unordered_map<int, vector<int>>());\n        // Actually calculates the people skill masks, as well as add to the skill list\n        for (int i = 0; i < m; i++) {\n            int mask = 0;\n            for (string skill : people[i]) {\n                withSkill[skillToIndex[skill]].push_back(i);\n                mask += 1 << skillToIndex[skill];\n            }\n            peopleSkillMask.push_back(mask);\n        }\n\n        // Starting from the first skill, with no skills found, find the minimum set of people\n        return dfs(0, 0, peopleSkillMask, withSkill, seenSkill);\n    }\n};\n```\n![image.png](https://assets.leetcode.com/users/images/8f194500-137f-469d-a287-81431bf232fd_1689536290.021077.png)\n
['Recursion', 'Memoization', 'Bitmask', 'C++']