Java DFS search with Pruning, using Bitwise tricks, 4ms, beating 98%
My basic idea is just to use DFS search to find the combination of people which covers all skills and having the least number. During the search, I keep a list 
My basic idea is just to use DFS search to find the combination of people which covers all skills and having the least number. During the search, I keep a list named `sol` to record the current optimal combination, and another list named `onesol`, which keeps adding and removing person, to represent the current team. This process is the same as backtracking.\n\nBecause there\'s at most 16 skills, I use a bitmask number `cur` to represent all the coverred skills with the current team. Each bit of `cur` represents a skill: 1 means the team has it, 0 means not. So in the dfs function, first you check if cur has all bits of 1. If it does, the current team, `onesol`, is a possible solution. We just need to compare if its size is smaller than `sol`, and save it if it is.\n\nAnother optimization is to prune the search process, when the current team `onesol` has more people than the current optimal team `sol`, we don\'t have to keep searching further.\n\n```\nclass Solution {\n    List<Integer> sol = new ArrayList<>();\n    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {\n        Map<String, Integer> idx = new HashMap<>(); \n        int n = 0;\n        for (String s : req_skills) idx.put(s, n++);///skills are represented by 0, 1, 2....\n        int[] pe = new int[people.size()];\n        for (int i = 0; i < pe.length; i++) {\n            for (String p : people.get(i)) {\n                int skill = idx.get(p);\n                pe[i] += 1 << skill;\n            }\n        } // each person is transferred to a number, of which the bits of 1 means the guy has the skill\n        search(0, pe, new ArrayList<Integer>(), n);  \n        int[] ans = new int[sol.size()];\n        for (int i = 0; i < sol.size(); i++) ans[i] = sol.get(i);\n        return ans;\n    }\n    \n    public void search(int cur, int[] pe, List<Integer> onesol, int n) { \n        if (cur == (1<<n) - 1) {  // when all bits are 1, all skills are coverred\n            if (sol.size() == 0 || onesol.size() < sol.size()) {\n                sol = new ArrayList<>(onesol);\n            }\n            return;\n        }\n        if (sol.size() != 0 && onesol.size() >= sol.size()) return;    //pruning\n        int zeroBit = 0;\n        while (((cur>>zeroBit)&1) == 1) zeroBit++;   \n        for (int i = 0; i < pe.length; i++) {\n            int per = pe[i];\n            if (((per>>zeroBit)&1) == 1) {\n                onesol.add(i); // when a person can cover a zero bit in the current number, we can add him\n                search(cur|per, pe, onesol, n);\n                onesol.remove(onesol.size() - 1);  //search in a backtracking way\n            }\n        } \n    }\n}\n```
[]