Python - Optimized backtracking with explanation and code comments [88 ms]
The first important observation to make is that this problem has that NP-Complete feeling around it. With that, we know that we\'re probably looking at a pseudo
The first important observation to make is that this problem has that NP-Complete feeling around it. With that, we know that we\'re probably looking at a pseudo-polynomial algorithm at best (e.g. dynamic programming), or a well optimised non-polynomial algorithm. Given how small the number of skills is, and the number of people, the latter should seem more likely. Therefore, we should be focussing on the best way of doing that, rather than trying to find a true polynomial approach.\n\nThe approach I took was a backtracking one. Using a map of skills to people with them and a set of currently unmet skills, go through each skill, considering each person that could perform the skill. Remove all skills that person can perform from the unmet skills set, recursively call on the next skill, and then afterwards return the person\'s skills to the unmet set (backtracking).\n\nIn order to speed it up a bit, I made one other improvement. Before doing the backtracking, the algorithm clears the skill sets of all people who are a subset of another. The sets are replaced with an empty set so that indexes aren\'t messed up (which would lead to a lot of bother and hassle having to maintain a map, for no efficiency improvement)\n\nLooking at Wikipedia afterwards, this is indeed the [Set Cover Problem](https://en.wikipedia.org/wiki/Set_cover_problem), an NP Complete problem.\n\nIn terms of run time, this algorithm completed in 88 ms, which is probably comparable to the DP approaches. The optimizations at the start make a big difference! (Without them, it\'s TLE)\n\nComments are in the code. Reading through that is probably the easiest way to understand. Enjoy!\n\n```\nclass Solution:\n    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n        \n        # Firstly, convert all the sublists in people into sets for easier processing.\n        for i, skills in enumerate(people):\n            people[i] = set(skills)\n        \n        # Remove all skill sets that are subset of another skillset, by replacing the subset with an\n        # empty set. We do this rather than completely removing, so that indexes aren\'t \n        # disrupted (which is a pain to have to sort out later).\n        for i, i_skills in enumerate(people):\n            for j, j_skills in enumerate(people):\n                if i != j and i_skills.issubset(j_skills):\n                    people[i] = set()\n        \n        # Now build up a dictionary of skills to the people who can perform them. The backtracking algorithm\n        # will use this.\n        skills_to_people = collections.defaultdict(set)\n        for i, skills in enumerate(people):\n            for skill in skills:\n                skills_to_people[skill].add(i)\n            people[i] = set(skills)\n        \n        # Keep track of some data used by the backtracking algorithm.\n        self.unmet_skills = set(req_skills) # Backtracking will remove and readd skills here as needed.\n        self.smallest_length = math.inf # Smallest team length so far.\n        self.current_team = [] # Current team members.\n        self.best_team = [] # Best team we\'ve found, i,e, shortest team that covers skills/\n        \n\t\t# Here is the backtracking algorithm.\n        def meet_skill(skill=0):\n\t\t\t# Base case: All skills are met.\n            if not self.unmet_skills:\n\t\t\t\t# If the current team is smaller than the previous we found, update it.\n                if self.smallest_length > len(self.current_team):\n                    self.smallest_length = len(self.current_team)\n                    self.best_team = self.current_team[::] # In Python, this makes a copy of a list.\n                return # So that we don\'t carry out the rest of the algorithm.\n                        \n            # If this skill is already met, move onto the next one.\n            if req_skills[skill] not in self.unmet_skills:\n                return meet_skill(skill + 1)\n\t\t\t\t# Note return is just to stop rest of code here running. Return values\n\t\t\t\t# are not caught and used.\n            \n            # Otherwise, consider all who could meet the current skill.\n            for i in skills_to_people[req_skills[skill]]:\n                \n\t\t\t\t# Add this person onto the team by updating the backtrading data.\n                skills_added_by_person = people[i].intersection(self.unmet_skills)\n                self.unmet_skills = self.unmet_skills - skills_added_by_person\n                self.current_team.append(i)\n                \n\t\t\t\t# Do the recursive call to further build the team.\n                meet_skill(skill + 1)\n                \n                # Backtrack by removing the person from the team again.\n                self.current_team.pop()\n                self.unmet_skills = self.unmet_skills.union(skills_added_by_person)\n        \n\t\t# Kick off the algorithm.\n        meet_skill()        \n        return self.best_team \n```
['Backtracking', 'Python3']