[Java] 3 Solutions - Knapsack Like DP & BFS & DFS
1 DP\n this is essentially a Knapsack problem, where your bag capacity is 2^(skill size) - 1\n\t 1st & 2nd block helps to convert people\'s skill sets to bitmas
#1 DP\n* this is essentially a Knapsack problem, where your bag capacity is ***2^(skill size) - 1***\n\t* 1st & 2nd block helps to convert people\'s skill sets to bitmasks\n\t* 3rd block is the DP computation\n\t* 4th block is to convert DP result to int[]\n```\nclass Solution {\n    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {\n        int ns = req_skills.length, np = people.size();\n        \n        Map<String, Integer> map = new HashMap<>(); // skill name <-> skill id\n        int skillId = 0;\n        for (String s : req_skills) {\n            map.put(s, skillId++);\n        }\n        \n        int[] ppl = new int[np]; // represents state (owing skill set) for each person, e.g. 0101 means person owns skill #1 and #3\n        int index = 0;\n        for (List<String> list : people) {\n            int state = 0;\n            for (String s : list) {\n                state |= (1 << map.get(s));\n            }\n            ppl[index++] = state;\n        }\n        \n        long[] dp = new long[1<<ns];\n        Arrays.fill(dp, Long.MAX_VALUE);\n        dp[0] = 0;\n        for (int i = 1; i <= np; i++) {\n            for (int j = 0; j < (1<<ns); j++) {\n                if (((j|ppl[i-1]) ^ j) > 0 // if person i - 1 can contribute at least 1 skill\n                    && Long.bitCount(dp[j|ppl[i-1]]) > Long.bitCount(dp[j]) + 1) {\n                    // selecting person i-1 would make state j|ppl[i-1] have less people count, go for it\n                    dp[j|ppl[i-1]] = dp[j] | (1l << (i - 1));\n                }\n            }\n        }\n        \n        // convert DP state to returned array\n        // e.g. 0b11010 means 1st, 3rd and 4th person are chosen\n        long result = dp[(1<<ns)-1];\n        int[] res = new int[Long.bitCount(result)];\n        int shift = 0;\n        index = 0;\n        while (result > 0) {\n            if ((result & 1) == 1) {\n                res[index++] = shift;\n            }\n            shift++;\n            result >>= 1;\n        }\n        return res;\n    }\n}\n```\n\n#2 BFS\n```\nclass Solution {\n    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {\n        int ns = req_skills.length, np = people.size();\n        \n        Map<String, Integer> map = new HashMap<>(); // skill name <-> skill id\n        int skillId = 0;\n        for (String s : req_skills) {\n            map.put(s, skillId++);\n        }\n        \n        int[] ppl = new int[np]; // represents state (owing skills set) for each person\n        int index = 0;\n        for (List<String> list : people) {\n            int state = 0;\n            for (String s : list) {\n                state |= (1 << map.get(s));\n            }\n            ppl[index++] = state;\n        }\n        \n        int target = (1 << ns) - 1;\n        \n        Set<Integer> visited = new HashSet<>();\n        Queue<Move> queue = new LinkedList<>();\n        queue.offer(new Move(0, 0));\n        visited.add(0);\n        while (!queue.isEmpty()) {\n            int size = queue.size();\n            for (int nn = 0; nn < size; nn++) {\n                Move cur = queue.poll();\n                for (int i = 0; i < np; i++) {\n                    if ((cur.ppl & (1l << i)) == 0) { // person i is not chosen yet\n                        long ppl_new = cur.ppl | (1l << i);\n                        int state_new = cur.state | ppl[i];\n                        if (state_new == target) {\n                            return getResultFromPeopleMask(ppl_new);\n                        }\n                        if (!visited.contains(state_new)) {\n                            visited.add(state_new);\n                            queue.offer(new Move(state_new, ppl_new));\n                        }\n                    }\n                }\n            }\n        }\n        return new int[0];\n    }\n    \n    private int[] getResultFromPeopleMask(long v) {\n        int[] res = new int[Long.bitCount(v)];\n        int shift = 0, index = 0;\n        while (v > 0) {\n            if ((v & 1) == 1) {\n                res[index++] = shift;\n            }\n            shift++;\n            v >>= 1;\n        }\n        return res;\n    }\n    \n    class Move {\n        int state;\n        long ppl;\n        \n        public Move(int state, long ppl) {\n            this.state = state;\n            this.ppl = ppl;\n        }\n    }\n}\n```
[]