java , c++ , phython 🔥 || ✅beats 100%   || with explanation || bitmasking and backtracking 🔥 🔥
understanding problem \nThe problem at hand is to find the smallest team of people who collectively possess all the required skills. to tackles this problem we 
# understanding problem \nThe problem at hand is to find the smallest team of people who collectively possess all the required skills. to tackles this problem we use  combination of bitmasking and backtracking\n# analogy and approach is given below the code !!\n# please upvote and comment for the hard work gyuz !!\n![upvote.jpg](https://assets.leetcode.com/users/images/297d1c04-5f3d-4166-953d-39c9692aa8ab_1689468276.837644.jpeg)\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n# Code\n\n```java []\nclass Solution {\n    List<Integer> mainTeam = new ArrayList<>();\n    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {\n        HashMap<String, Integer> map = new HashMap<>();\n        int i = 0;\n        for( String skill : req_skills) \n            map.put(skill,i++);\n\n        int reqSkills = (1<<i) -1;\n        //System.out.println(reqSkills);\n        int skills[] = getPeopleSkillsMask(people, map);\n        List<Integer> localTeam = new ArrayList<>();\n        findTeam(reqSkills, skills, 0, 0, localTeam);\n        //System.out.println("mt"+mainTeam);\n        return convertListToArray();\n\n    }\n    int[] getPeopleSkillsMask(List<List<String>> people,HashMap<String, Integer> map )\n    {\n        int len = people.size();\n        int skills[] = new int[len];\n        for( int i = 0; i < len; i++)\n        {\n            for( String skill : people.get(i)) \n                skills[i] |= (1<<map.get(skill));\n            //System.out.println(i+" , "+skills[i]);\n        }\n        return skills;\n    }\n\n    void findTeam(int reqSkills, int[] skills, int teamSkills, int person, List<Integer> localTeam )\n    {\n        if( mainTeam.size() >0 && localTeam.size() >= mainTeam.size()-1 ||  person == skills.length)//early stopping\n            return ;\n\n        //taking current person into team\n        localTeam.add(person);\n\n        if( (teamSkills|skills[person]) == reqSkills)\n        {\n            // if( mainTeam.size() == 0 || localTeam.size() < mainTeam.size())\n            mainTeam = new ArrayList<Integer>(localTeam);\n            //System.out.println(teamSkills+" , "+person+" , "+localTeam+" mt "+mainTeam);\n            localTeam.remove(localTeam.size()-1);\n            return;\n        }\n        else if( (teamSkills|skills[person]) > teamSkills){\n            //System.out.println(teamSkills+" , "+person+" , "+localTeam+" mt "+mainTeam);\n            findTeam(reqSkills, skills, teamSkills|skills[person], person+1, localTeam );\n        }\n\n        localTeam.remove(localTeam.size()-1);\n\n        findTeam(reqSkills, skills, teamSkills, person+1, localTeam );\n    }\n    int[] convertListToArray()\n    {\n        int len = mainTeam.size();\n        int skills[] = new int[len];\n        //System.out.println("arra"+mainTeam);\n        for( int i = 0; i < len; i++)\n            skills[i] = mainTeam.get(i);\n        return skills;\n    }\n}\n```\n```cpp  []\nclass Solution {\npublic:\n    std::vector<int> smallestSufficientTeam(std::vector<std::string>& req_skills, std::vector<std::vector<std::string>>& people) {\n        int n = req_skills.size();\n        int m = people.size();\n        \n        std::unordered_map<std::string, int> skillToIndex;\n        for (int i = 0; i < n; i++) {\n            skillToIndex[req_skills[i]] = i;\n        }\n        \n        std::vector<int> arr(m, 0);\n        for (int i = 0; i < m; i++) {\n            std::vector<std::string>& personSkills = people[i];\n            int val = 0;\n            for (const std::string& skill : personSkills) {\n                val |= 1 << skillToIndex[skill];\n            }\n            arr[i] = val;\n        }\n        \n        std::vector<bool> banned(m, false);\n        for (int i = 0; i < m; i++) {\n            for (int j = i + 1; j < m; j++) {\n                int val = arr[i] | arr[j];\n                if (val == arr[i]) {\n                    banned[j] = true;\n                }\n                else if (val == arr[j]) {\n                    banned[i] = true;\n                }\n            }\n        }\n        \n        std::vector<int> ans;\n        helper(0, n, arr, std::vector<int>(), banned, ans);\n        \n        return ans;\n    }\n    \nprivate:\n    void helper(int cur, int n, const std::vector<int>& arr, std::vector<int> team, const std::vector<bool>& banned, std::vector<int>& ans) {\n        if (cur == (1 << n) - 1) {\n            if (ans.empty() || team.size() < ans.size()) {\n                ans = team;\n            }\n            return;\n        }\n        \n        if (!ans.empty() && team.size() >= ans.size()) {\n            return;\n        }\n        \n        int zero = 0;\n        while (((cur >> zero) & 1) == 1) {\n            zero++;\n        }\n        \n        for (int i = 0; i < arr.size(); i++) {\n            if (banned[i]) {\n                continue;\n            }\n            \n            if (((arr[i] >> zero) & 1) == 1) {\n                team.push_back(i);\n                helper(cur | arr[i], n, arr, team, banned, ans);\n                team.pop_back();\n            }\n        }\n    }\n};\n```\n\n```python []\nclass Solution(object):\n    def smallestSufficientTeam(self, req_skills, people):\n        """\n        :type req_skills: List[str]\n        :type people: List[List[str]]\n        :rtype: List[int]\n        """\n        mainTeam = []\n        map = {}\n        i = 0\n        for skill in req_skills:\n            map[skill] = i\n            i += 1\n\n        reqSkills = (1 << i) - 1\n        skills = self.getPeopleSkillsMask(people, map)\n        localTeam = []\n        self.findTeam(reqSkills, skills, 0, 0, localTeam, mainTeam)\n        return mainTeam\n\n    def getPeopleSkillsMask(self, people, map):\n        skills = []\n        for person in people:\n            skillMask = 0\n            for skill in person:\n                skillMask |= 1 << map[skill]\n            skills.append(skillMask)\n        return skills\n\n    def findTeam(self, reqSkills, skills, teamSkills, person, localTeam, mainTeam):\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            if len(mainTeam) == 0 or len(localTeam) < len(mainTeam):\n                mainTeam[:] = localTeam[:]\n            localTeam.pop()\n            return\n        elif (teamSkills | skills[person]) > teamSkills:\n            self.findTeam(reqSkills, skills, teamSkills | skills[person], person + 1, localTeam, mainTeam)\n\n        localTeam.pop()\n        self.findTeam(reqSkills, skills, teamSkills, person + 1, localTeam, mainTeam)\n\n```\n\n\n    \n# Analogy \n```\nSkills:                   People:\n-------                   -------\n[0] Programming           [0] Person 1:-> [0] Programming, Design\n[1] Design                [1] Person 2:-> [1] Design, Marketing\n[2] Marketing             [2] Person 3:-> [2] Programming, Marketing\n\n```\nImagine you\'re planning a grand treasure hunt with a bunch of friends. Each friend has a set of unique skills that will come in handy during the adventure. Your goal is to form the smallest team possible that can cover all the required skills for the treasure hunt.\n\nHere\'s how the analogy relates to the code:\n\nEach friend represents a person in the code, and their skills correspond to the skills array.\nThe skills needed for the treasure hunt are like the required skills in the problem.\nTo efficiently keep track of everyone\'s skills, you give each friend a special bracelet with switches. Each switch represents a particular skill. If a switch is ON, it means the friend has that skill; otherwise, it\'s OFF.\nNow, you create a map that links each skill to its corresponding switch on the bracelet. This way, you can easily identify the position of a skill on the bracelet when needed. It\'s like having a cheat sheet or a skills-to-switch mapping.\nOnce you\'ve set up the bracelet and the mapping, you go through each friend\'s skills, one by one, and toggle the corresponding switch on their bracelet. It\'s like saying, "Hey, this friend has this skill!" You do this for each friend, and you end up with an array of bracelets, where each bracelet represents a person\'s skills.\nNow, to optimize the team formation, you check for any redundant skills among your friends. You compare the bracelets of different pairs of friends. If you find a pair where one friend\'s skills are already covered by another friend\'s skills, you mark the redundant friend as "banned." It\'s like saying, "We don\'t need this friend on the team because their skills are already covered by someone else!"\nWith the bracelets and the ban list ready, you start forming the smallest team possible. You begin by examining the bracelets of different friends and checking if all the required skills for the treasure hunt are already covered by the current team. If they are, you compare the size of the current team with the smallest team found so far. If the current team is smaller, you update the smallest team accordingly.\nTo speed up the search, you keep track of the size of the smallest team found so far. If the current team\'s size is already greater than or equal to the smallest team size, you stop searching because you\'ve already found a smaller team.\nNow, you focus on the next required skill for the treasure hunt and choose the friend with the corresponding switch that is still OFF. This helps narrow down the search and prioritize the skills that are still needed.\nYou go through each friend and check if they are not banned and have the required skill (switch ON). If they meet the conditions, you add them to the current team. It\'s like saying, "Hey, you\'re in! Join the team!"\nThen, you repeat the process, going through different combinations of friends, until you\'ve explored all the possibilities and found the smallest team that covers all the required skills for the treasure hunt.\nFinally, you announce the final team, converting it from a list of friends to an array. You say, "Here\'s the smallest team that has all the skills covered! Let\'s go on this epic treasure hunt together!"\nSo, in this analogy, the code is like the mastermind behind forming the optimal treasure hunt team. It uses the bracelets and the ban list to efficiently search for the smallest team with all the required skills.\n# (first try to read the analogy it can help if have porblem in only not understanding the question )\n# Apporach \nPicture this: you\'re putting together a dream team for an epic adventure. Each person in the team has their own set of unique skills that are crucial for the mission. The goal is to find the smallest team possible that covers all the necessary skills.\n- First, it sets up a system where each person\'s skills are like a bunch of switches. If a switch is ON, it means the person has that skill; if it\'s OFF, they don\'t possess it. It\'s like each person has their own switchboard!\n- To keep things organized, the code creates a cheat sheet called the "skills-to-switch mapping." It\'s like a quick reference guide that matches each skill to its corresponding switch. This makes it easy to find the right switch position for each skill.\n- Once the mapping is ready, the code goes through the list of people. It checks each person\'s skills and flips the corresponding switches on their switchboard. It\'s like saying, "Hey, this person has this skill!" By doing this for each person, we end up with a clever array that represents everyone\'s skills using these switchboards.\n- Now, to optimize the team-building process, the code checks for redundancy. It compares the switchboards of different people to see if one person\'s skills are already covered by someone else. If that\'s the case, the redundant person is marked as "banned." It\'s like saying, "Hey, we don\'t need this person because their skills are already covered by someone else on the team!"\n\n- With the switchboards and the ban list in hand, the code jumps into the helper method. This method is like a detective that tries to find the smallest team of people with all the necessary skills.\n- The detective first checks if all the required skills are already covered by looking at the current state of the switchboards. If they are, the detective compares the size of the current team with the smallest team found so far. If the current team is smaller, it becomes the new smallest team. It\'s like saying, "Wow, this team is even smaller and still has all the skills we need!"\n\n- To speed up the search, the detective keeps track of the size of the smallest team found so far. If the current team\'s size is already equal to or bigger than the smallest team size, there\'s no point in searching further. We\'ve already got a smaller team.\n\n- The detective then focuses on the next required skill by finding the first switch that is still OFF. This helps narrow down the search and prioritize the skills we still need to cover.\n\n- Going through the remaining candidates, the detective checks if they are not banned and possess the required skill. If they meet the conditions, they get added to the current team. It\'s like saying, "Hey, you\'re in! Join the team and bring your awesome skills!"\n- The detective repeats this process, exploring different combinations of people, until every possibility has been considered. Eventually, the detective finds the smallest team that covers all the required skills.\n\n- Finally, the code converts the smallest team into an array and presents it as the ultimate dream team. It\'s like saying, "Here\'s the smallest team that has all the skills covered. Get ready for an incredible adventure!"\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n
['Java']