Java - Recursive + Memorization (Explanation)
Idea \n  we have 2 choices for each person :\n1. include current person , and add his skill to current skillset & find min persons needed from next person index
# Idea \n  we have 2 choices for each person :\n1. **include current person** , and add his skill to current skillset & find min persons needed from next person index with updated current skillset\n2. **ignore current person** , and move to finding min persons needed from next person index \n3. return min of both the ways - **including current person** or **ignoring current person** .\n\n- Used to dp to store subproblem answers.\n- Time complexity (2^M * N) where M is skills count, N is persons count\n# Code\n```\nclass Solution {\n\n    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {\n        \n        int personsSize = people.size();\n        int skillsCount = req_skills.length;\n\n\n        HashMap<String, Integer> skillId = new HashMap<String, Integer>();\n        for (int i = 0; i < skillsCount; i++) {\n            skillId.put(req_skills[i], i);\n        }\n\n        int skillsMaskOfPerson[] = new int[personsSize]; // skill mask of each person\n        for (int i = 0; i < personsSize; i++) {\n            for (String skill : people.get(i)) {\n                skillsMaskOfPerson[i] |= 1 << skillId.get(skill);\n            }\n        }\n\n        long personsMask =  solve(skillsMaskOfPerson,0, req_skills.length, 0 , new HashMap<Long,Long>());\n\n        return unmaskPersons(personsMask,personsSize);\n    }\n\n  \n    public long solve(int[] skillsMaskOfPerson , int currentSkillsMask, int totalSkills, int currentPersonIndex, HashMap<Long,Long> dp){\n        int N = skillsMaskOfPerson.length;\n\n        if(Integer.bitCount(currentSkillsMask) == totalSkills)\n            return 0;  // no more persons needed for us, since we have all skills covered. \n\n        if(currentPersonIndex == N){\n            return Long.MAX_VALUE;\n        }\n\n        long dpKey = (currentSkillsMask << 16) | currentPersonIndex; // from right, first 16 bits for currentPersonIndex, and next 16 bits for skills mask\n\n        if(dp.containsKey(dpKey))\n            return dp.get(dpKey);\n    \n        // (1L<<currentPersonIndex) => this is to include current person in the solution (basically, if the person has index i, we are setting ith bit to 1 from right);\n        // (currentSkillsMask | skillsMaskOfPerson[currentPersonIndex]) => including current person\'s skills in the our skillmask \n        long includeCurrentPerson = (1L<<currentPersonIndex) | solve(skillsMaskOfPerson, \n                                    (currentSkillsMask |skillsMaskOfPerson[currentPersonIndex]),\n                                    totalSkills, currentPersonIndex+1,dp); \n        long ignoreCurrentPerson =  solve(skillsMaskOfPerson, currentSkillsMask, totalSkills, currentPersonIndex+1, dp);\n\n        dp.put(dpKey, (Long.bitCount(includeCurrentPerson) < Long.bitCount(ignoreCurrentPerson)) ? \n            includeCurrentPerson : ignoreCurrentPerson);\n        \n        return dp.get(dpKey);\n\n    }\n\n    long getDPKey(long skillMask, long currentPersonIndex){\n        return  ((skillMask << 16) | currentPersonIndex);\n    }\n\n\n    public int[] unmaskPersons(long personsMask, int numberOfPeoples){\n            int[] res = new int[Long.bitCount(personsMask)];\n            int index = 0;\n            for(int i=1;i<=numberOfPeoples;i++){\n                if(((personsMask>>(i-1)) & 1 ) == 1){\n                    res[index++] = i-1;\n                    if(index == res.length)\n                        break;\n                }\n            }\n            return res;\n    }\n\n}\n```
['Dynamic Programming', 'Bit Manipulation', 'Recursion', 'Bitmask', 'Java']