🙌 | Fully Explained | 🔥 | Optimized Java and Python Solution | ✨ | Easy Method | ✅
\n\n_\n# Java Code Explanation\n## Intuition - \nThe code aims to solve a problem where we need to find the smallest team of candidates who possess all the requ
![image.png](https://assets.leetcode.com/users/images/77aa38ff-af30-4794-916a-3e83312fd9b0_1689489541.9235916.png)\n\n_________\n# Java Code Explanation\n## Intuition - \nThe code aims to solve a problem where we need to find the smallest team of candidates who possess all the required skills. We want to build a team that covers all the skills needed for a project, minimizing the number of team members.\n\n## Approach - \n1. First, we create a mapping of skills to indices. This mapping helps us associate each skill with a unique number.\n2. We represent the required skills as a bitmask. A bitmask is a binary number that represents the presence or absence of each skill. It helps us efficiently check if a set of candidates has all the required skills.\n3. Next, we convert the skills of each candidate into a bitmask using the skills mapping. This step helps us represent the skills of each candidate in a compact way.\n4. We use a recursive function called `findTeam` to search for the smallest team that covers all the required skills. The function explores different combinations of candidates to find the optimal team.\n5. Inside the `findTeam` function, we check if the current team covers all the required skills. If it does, we update the `mainTeam` with the new smallest team found so far.\n6. We recursively explore the remaining candidates, considering both the case of including the current candidate and excluding them. This exploration helps us find the best combination of candidates that covers all the required skills.\n7. Finally, we convert the `mainTeam` from a list to an array and return it as the result.\n\n## Complexity Analysis -\n - The time complexity of the given code is exponential, specifically **O(2^n),** where n is the number of candidates. This is because the recursive function `findTeam` explores all possible combinations of candidates to find the smallest team that covers all the required skills.\n\n - The space complexity of the code is **O(n),** where n is the number of candidates. This is due to the space used to store the `mainTeam` and `localTeam` lists during the recursive process. The space used for these lists grows with the number of candidates but does not exceed it.\n\n__________________________________________________________\n\n# Python Code Explanation\n\n## Intuition - \nThe program aims to find the smallest team of candidates that collectively possess all the required skills. It uses a bitmasking approach to represent skills and employs backtracking to explore different combinations of candidates.\n\n## Approach - \n1. Create a skills mapping using a dictionary called `skillsMap`, associating each skill with a unique index.\n2. Generate a bitmask, `requiredSkillsMask`, representing all the required skills. This bitmask is used to check if a candidate team possesses all the necessary skills.\n3. Convert the skills of each candidate into a bitmask representation using the `getPeopleSkillsMask` function. Iterate through each candidate\'s skills and set the corresponding bit in their bitmask based on the `skillsMap`.\n4. Initialize an empty `mainTeam` list to store the current smallest team and a `localTeam` list to track the candidates being considered in the current recursive branch.\n5. Utilize the `findTeam` recursive function to search for the smallest team. The function explores different combinations of candidates to find a team that covers all the required skills.\n6. Within the `findTeam` function, check if the current team covers all the required skills. If so, update the `mainTeam` with the new smallest team found.\n7. Recursively explore the remaining candidates, considering both the inclusion and exclusion of the current candidate, to find the optimal team.\n8. Convert the `mainTeam` list to an array using the `convertListToArray` function and return it as the result.\n\n\n## Complexity - \n - The Time Complexity of the program is exponential, specifically **O(2^n),** where n is the number of candidates. This is because the program explores all possible combinations of candidates to find the smallest team that covers all the required skills.\n\n - The Space Complexity is **O(n),** where n is the number of candidates, due to the space used by the `mainTeam` and `localTeam` lists during the recursive process. The space used grows with the number of candidates but does not exceed it.\n\n _____________________________________\n\n# Code\n``` Java []\nclass Solution {\n    List<Integer> mainTeam = new ArrayList<>();\n    public int[] smallestSufficientTeam(String[] requiredSkills, List<List<String>> candidates) {\n        HashMap<String, Integer> skillsMap = new HashMap<>();\n        int skillIndex = 0;\n        for (String skill : requiredSkills) {\n            skillsMap.put(skill, skillIndex++);\n        }\n        int requiredSkillsMask = (1 << skillIndex) - 1;\n        int[] candidatesSkills = getCandidatesSkillsMask(candidates, skillsMap);\n        List<Integer> localTeam = new ArrayList<>();\n        findTeam(requiredSkillsMask, candidatesSkills, 0, 0, localTeam);\n        return convertListToArray();\n    }\n    int[] getCandidatesSkillsMask(List<List<String>> candidates, HashMap<String, Integer> skillsMap) {\n        int numOfCandidates = candidates.size();\n        int[] candidatesSkills = new int[numOfCandidates];\n        for (int i = 0; i < numOfCandidates; i++) {\n            for (String skill : candidates.get(i)) {\n                candidatesSkills[i] |= (1 << skillsMap.get(skill));\n            }\n        }\n        return candidatesSkills;\n    }\n    void findTeam(int requiredSkillsMask, int[] candidatesSkills, int teamSkills, int personIndex, List<Integer> localTeam) {\n        if (mainTeam.size() > 0 && localTeam.size() >= mainTeam.size() - 1 || personIndex == candidatesSkills.length) {\n            return;\n        }\n        localTeam.add(personIndex);\n        if ((teamSkills | candidatesSkills[personIndex]) == requiredSkillsMask) {\n            mainTeam = new ArrayList<Integer>(localTeam);\n            localTeam.remove(localTeam.size() - 1);\n            return;\n        } else if ((teamSkills | candidatesSkills[personIndex]) > teamSkills) {\n            findTeam(requiredSkillsMask, candidatesSkills, teamSkills | candidatesSkills[personIndex], personIndex + 1, localTeam);\n        }\n        localTeam.remove(localTeam.size() - 1);\n        findTeam(requiredSkillsMask, candidatesSkills, teamSkills, personIndex + 1, localTeam);\n    }\n    int[] convertListToArray() {\n        int teamSize = mainTeam.size();\n        int[] teamSkillsArray = new int[teamSize];\n        for (int i = 0; i < teamSize; i++) {\n            teamSkillsArray[i] = mainTeam.get(i);\n        }\n        return teamSkillsArray;\n    }\n}\n```\n\n``` Python []\nclass Solution:\n    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n        skillsMap = {}\n        skillIndex = 0\n        for skill in req_skills:\n            skillsMap[skill] = skillIndex\n            skillIndex += 1\n\n        requiredSkillsMask = (1 << skillIndex) - 1\n        candidatesSkills = self.getPeopleSkillsMask(people, skillsMap)\n        self.mainTeam = []  \n        localTeam = []\n        self.findTeam(requiredSkillsMask, candidatesSkills, 0, 0, localTeam)\n        return self.convertListToArray()\n\n    def getPeopleSkillsMask(self, people: List[List[str]], skillsMap: dict) -> List[int]:\n        numOfPeople = len(people)\n        peopleSkills = [0] * numOfPeople\n        for i in range(numOfPeople):\n            for skill in people[i]:\n                peopleSkills[i] |= (1 << skillsMap[skill])\n        return peopleSkills\n\n    def findTeam(self, reqSkills: int, skills: List[int], teamSkills: int, person: int, localTeam: List[int]) -> None:\n        if hasattr(self, "mainTeam"): \n            mainTeam = self.mainTeam\n        else:\n            mainTeam = []\n        \n        if len(mainTeam) > 0 and len(localTeam) >= len(mainTeam) - 1 or person == len(skills):\n            return\n\n        localTeam.append(person)\n\n        if (teamSkills | skills[person]) == reqSkills:\n            mainTeam.clear()\n            mainTeam.extend(localTeam)\n            localTeam.pop()\n            return\n        elif (teamSkills | skills[person]) > teamSkills:\n            self.findTeam(reqSkills, skills, teamSkills | skills[person], person + 1, localTeam)\n\n        localTeam.pop()\n        self.findTeam(reqSkills, skills, teamSkills, person + 1, localTeam)\n\n    def convertListToArray(self) -> List[int]:\n        mainTeam = self.mainTeam\n        teamSize = len(mainTeam)\n        teamSkillsArray = [0] * teamSize\n        for i in range(teamSize):\n            teamSkillsArray[i] = mainTeam[i]\n        return teamSkillsArray\n```
['Dynamic Programming', 'Bit Manipulation', 'Bitmask', 'Python', 'Java']