Java - Bitmask (Naive BFS)
Took me weeks to solve this problem... it\'s my first Hard leetcode problem, and my first ever forray into either bitmasks or Dynamic Programming. Though I don\
Took me weeks to solve this problem... it\'s my first Hard leetcode problem, and my first ever forray into either bitmasks or Dynamic Programming. Though I don\'t think my solution technically employs DP, feeling very proud that it was accepted at all.\n\n```\nimport java.util.*;\n\nclass Problem {\n    // bit masks!\n    long currentTeam;\n    int metSkills;\n    int n;\n\n    Problem(long currentTeam, int metSkills, int n) {\n        this.currentTeam = currentTeam;\n        this.metSkills = metSkills;\n        this.n = n;\n    }\n}\n\nclass Solution {\n    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {\n        long solutionTeam = 0;\n\n        final int peopleSize = people.size();\n\n        // Bitmask of required skills - 11111 for 5 skills, etc.\n        final int requiredSkillsBitmask = Solution.requiredSkillsBitmask(req_skills.length);\n\n        // map of Person Index -> Skill Bitmap\n        HashMap<Integer, Integer> personToBitmaskMap = Solution.personToBitmaskMap(req_skills, people);\n\n        // LIFO Queue of subproblems - starting with initial problem\n        ArrayDeque<Problem> problems = new ArrayDeque<>();\n        problems.add(new Problem(0, 0, 0));\n        \n        problem_loop:\n        while (!problems.isEmpty()) {\n            Problem currentProblem = problems.pop();\n            int n = currentProblem.n;\n            int metSkills = currentProblem.metSkills;\n            long currentTeam = currentProblem.currentTeam;\n\n            for (int i = n; i < peopleSize; i +=1) {\n                long nextTeam = currentTeam | ((long) 1 << i);\n                int personSkills = personToBitmaskMap.get(i);\n                int nextMetSkills = metSkills | personSkills;\n\n\n                if (nextMetSkills == requiredSkillsBitmask) {\n                    solutionTeam = nextTeam;\n                    break problem_loop;\n                }\n                else if ((nextMetSkills | metSkills) != metSkills) {\n                    // add to subproblems\n                    problems.add(new Problem(nextTeam, nextMetSkills, i + 1));\n                }\n            }\n        }\n\n        ArrayList<Integer> resultList = new ArrayList<>();\n\n        // fill result team with indices\n        long teamMask = solutionTeam;\n        for (int i = 0; i < peopleSize; i += 1) {\n            if (teamMask % 2 == 1) {\n                resultList.add(i);\n                System.out.println("Person #" + i + "\\t: " + Integer.toBinaryString(personToBitmaskMap.get(i)));\n            }\n            teamMask = teamMask >> 1;\n        }\n\n        return resultList.stream().mapToInt(i -> i).toArray();\n    }\n\n\n    public static int requiredSkillsBitmask(int skillCount) {\n        int result = 1;\n        for (int i = 1; i < skillCount; i += 1) {\n            result = (result << 1) + 1;\n        }\n        return result;\n    }\n\n    // map of Person Index -> Skill Bitmap\n    public static HashMap<Integer, Integer> personToBitmaskMap(String[] req_skills, List<List<String>> people) {\n        HashMap<String, Integer> skillToBitmaskMap = Solution.skillToBitmaskMap(req_skills);\n        HashMap<Integer, Integer> result = new HashMap<>();\n\n        int i = 0;\n        for (List<String> person : people) {\n            int skills = 0;\n            for (String skill : person) {\n                skills = skills | skillToBitmaskMap.get(skill);\n            }\n            result.put(i, skills);\n            i += 1;\n        }\n\n        return result;\n    }\n\n    // map of Skill String -> Skill bitmap\n    public static HashMap<String, Integer> skillToBitmaskMap(String[] req_skills) {\n        HashMap<String, Integer> result = new HashMap<>();\n        for (int i = 0; i < req_skills.length; i += 1) {\n            result.put(req_skills[i], 1 << i);\n        }\n        return result;\n    }\n}\n```
[]