1ms solution || JAVA CODE USING BITMASK
JAVA CODE USING BITMASK\n\n# Code\n\nclass Solution {\n\n    int allSkills;\n    People[] peoples;\n    Team minTeam = new Team(0, 0);\n\n    public int[] small
# JAVA CODE USING BITMASK\n\n# Code\n```\nclass Solution {\n\n    int allSkills;\n    People[] peoples;\n    Team minTeam = new Team(0, 0);\n\n    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> peoples_list) {\n\n        // Map from skill string to its bit representation\n        // skills[0] -> 1\n        // skills[1] -> 2\n        // skills[2] -> 4\n        Map<String, Integer> skills_map = new HashMap<>();\n        for (int index = 0; index < req_skills.length; index++) {\n            skills_map.put(req_skills[index], 1 << index);\n        }\n\n        // Bit mask for all skills\n        this.allSkills = (1 << req_skills.length) - 1;\n\n        // Create peoples, record original index, convert skills to bit mask\n        int peoplesCount = peoples_list.size();\n        People[] allpeoples = new People[peoplesCount];\n        for (int index = 0; index < peoplesCount; index++) {\n            int skills = 0;\n            for (String sk : peoples_list.get(index)) {\n                skills |= skills_map.get(sk);\n            }\n            // This people has all skills, return\n            if (skills == allSkills) {\n                return new int[] {index};\n            }\n            allpeoples[index] = new People(index, skills);\n        }\n\n        // Prune peoples, keep minimum set of peoples which have required skills\n        this.peoples = prune(allpeoples);\n\n        dfs(0, new Team(0, 0));\n\n        // `minTeam` contains the optimal smallest team\n        int[] result = new int[minTeam.count];\n        for (People people : peoples) {\n            if ((minTeam.peoples & people.mask) != 0) {\n                result[--minTeam.count] = people.index;\n            }\n        }\n\n        return result;\n    }\n\n    // If P1\'s set of skills is superset of P2, then P2 is pruned\n    // And obviously, peoples with empty set of skills are pruned\n    private People[] prune(People[] allpeoples) {\n        int peoplesCount = allpeoples.length;\n\n        People[] prunePeoples = new People[peoplesCount];\n        boolean[] prunes = new boolean[peoplesCount];\n        int pruneCount = 0;\n        for (int i = 0; i < peoplesCount; i++) {\n            if (prunes[i]) {\n                continue;\n            }\n            for (int j = i + 1; j < peoplesCount; j++) {\n                int intersects = allpeoples[i].skills & allpeoples[j].skills;\n                if (intersects == allpeoples[j].skills) {\n                    prunes[j] = true;\n                } else if (intersects == allpeoples[i].skills) {\n                    prunes[i] = true;\n                    break;\n                }\n            }\n            if (!prunes[i]) {\n                prunePeoples[pruneCount++] = allpeoples[i];\n            }\n        }\n\n        return Arrays.copyOf(prunePeoples, pruneCount);\n    }\n\n    private void dfs(int skillset, Team localTeam) {\n        \n        if (skillset == this.allSkills) {\n            // All skills filled, record optimal minTeam\n            if (minTeam.count == 0 || minTeam.count > localTeam.count) {\n                minTeam.peoples = localTeam.peoples;\n                minTeam.count = localTeam.count;\n            }\n            return;\n        }\n\n        for (People people : peoples) {\n\n             // Not an optimal team\n            if ((minTeam.count > 0 && minTeam.count <= localTeam.count + 1)\n                // This people has been added to team\n                || (localTeam.peoples & people.mask) != 0) {\n                continue;\n            }\n\n            // The right most missing skill required\n            int rightMostSkill = ~skillset & (skillset + 1);\n            if ((rightMostSkill & people.skills) != rightMostSkill) {\n                continue;\n            }\n\n            // Add people and skills to team, solve remaining skills\n            localTeam.peoples |= people.mask;\n            localTeam.count++;\n\n            dfs(skillset | people.skills, localTeam);\n\n            // Remove people from team to try other possibilities\n            localTeam.peoples ^= people.mask;\n            localTeam.count--;\n        }\n    }\n\n    static class Team {\n        // Bit mask for peoples in the team.\n        // Since there are at most 60 peoples, a 64 bits long is sufficient.\n        long peoples;\n\n        // Count of peoples in the team\n        int count;\n\n        Team(long peoples, int count) {\n            this.peoples = peoples;\n            this.count = count;\n        }\n    }\n\n    static class People {\n        // Original index of people\n        final int index;\n        // Bit mask for skills\n        final int skills;\n        // Bit mask for index\n        final long mask;\n\n        People(int index, int skills) {\n            this.index = index;\n            this.skills = skills;\n            this.mask = 1L << index;\n        }\n    }\n}\n```
['Java']