Java | Memoization | Explained
Idea:\n Create a map of skill to index. \n Use this map to create a bit-mask of skills for each person. This is possible as there are only 16 possible skills wh
**Idea:**\n* Create a map of skill to index. \n* Use this map to create a bit-mask of skills for each person. This is possible as there are only 16 possible skills which can fit in a 32 bit int\n* Start creating team and replacing it if a smaller team (which has all skills) has a smaller size \n* If the current team has a size greater or equal to a team with all skills seen previously, then there\'s no point in replacing. Exit immediately\n* If the final person hasn\'t been considered yet, then there are 2 possible decisions \n\t* exclude the person from the team\n\t* include the person in the team\n\t\t* Do this only if the person brings any new skill to the team. This can be achieved by logical ORing the person\'s skill-mask with the team\'s skill-mask and checking if the team\'s skill mask changes. If yes, then \n\t\t\t* Add this person to the team\n\t\t\t* Recurse with the updated team mask to find the next member\n\t\t\t* Remove this person from the team\n\t\t\t* This addition and removal is done because the same list will be used for the entire decision tree, so the decision must be localized and have no effect on other decision nodes. This is similar to what we do in backtracking\n* Else if the final person has been considered and the current team has all the required skills, then replace the current-valid-answer-team with this team\n\n**Method 1:** Brute force DFS. Gets TLE\n```\npublic int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {\n\tvar finalTeam = new ArrayList<Integer>();\n\tsmallestSufficientTeam(getSkillMasks(reqSkills, people), \n\t\t\t\t\t\t   (1 << reqSkills.length) - 1, \n\t\t\t\t\t\t   0, 0, new ArrayDeque<>(), finalTeam);\n\t\t\t\t\t\t   \n\treturn finalTeam.stream()\n\t\t\t\t\t.mapToInt(i -> i)\n\t\t\t\t\t.toArray();\n}\n\n// T/S: O(n)/O(n), where n = size(people)\nprivate int[] getSkillMasks(String[] reqSkills, List<List<String>> people) {\n\tvar skillMasks = new int[people.size()];\n\tvar skillIndex = new HashMap<String, Integer>();\n\n\tfor (var i = 0; i < reqSkills.length; i++)\n\t\tskillIndex.put(reqSkills[i], i);\n\n\tfor (var i = 0; i < people.size(); i++)\n\t\tfor (var skill : people.get(i))\n\t\t\tskillMasks[i] |= 1 << skillIndex.get(skill);\n\n\treturn skillMasks;\n}\n\nprivate void smallestSufficientTeam(int[] skillMasks, int targetSkills, int personIndex, int teamSkills, Deque<Integer> team, List<Integer> finalTeam) {\n\tif (!finalTeam.isEmpty() && team.size() == finalTeam.size())\n\t\treturn;\n\tif (personIndex < skillMasks.length) {\n\t\t// exclude\n\t\tsmallestSufficientTeam(skillMasks, targetSkills, personIndex + 1, teamSkills, team, finalTeam);\n\n\t\tvar newTeamSkills = teamSkills | skillMasks[personIndex];\n\t\tif (newTeamSkills != teamSkills) {\n\t\t\t// include\n\t\t\tteam.addLast(personIndex);\n\t\t\tsmallestSufficientTeam(skillMasks, targetSkills, personIndex + 1, newTeamSkills, team, finalTeam);\n\t\t\tteam.removeLast();\n\t\t}\n\t} else if (teamSkills == targetSkills) {\n\t\tfinalTeam.clear();\n\t\tfinalTeam.addAll(team);\n\t}\n}\n```\n\n**Method 2:** Inject memoization in method 1\n>**T/S:** O(n)/O(n), where n = size(people)\n>Note that size(reqSkills) \u2264 16, so any operation involving it takes O(1) time and space\n```\npublic int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {\n\tvar finalTeam = new ArrayList<Integer>();\n\tsmallestSufficientTeam(getSkillMasks(reqSkills, people), \n\t\t\t\t\t\t   (1 << reqSkills.length) - 1, \n\t\t\t\t\t\t   0, 0, new ArrayDeque<>(), finalTeam, \n\t\t\t\t\t \t   new HashMap<>());\n\t\t\t\t\t\t   \n\treturn finalTeam.stream()\n\t\t\t\t\t.mapToInt(i -> i)\n\t\t\t\t\t.toArray();\n}\n\nprivate void smallestSufficientTeam(int[] skillMasks, int targetSkills, int personIndex, int teamSkills, Deque<Integer> team, List<Integer> finalTeam, Map<Pair, Integer> memo) {\n\tif (!finalTeam.isEmpty() && team.size() == finalTeam.size())\n\t\treturn;\n\n\tvar key = new Pair(personIndex, teamSkills);\n\tif (memo.getOrDefault(key, Integer.MAX_VALUE) <= team.size())\n\t\treturn;\n\n\tif (personIndex < skillMasks.length) {\n\t\t// exclude\n\t\tsmallestSufficientTeam(skillMasks, targetSkills, personIndex + 1, teamSkills, team, finalTeam, memo);\n\n\t\tvar newTeamSkills = teamSkills | skillMasks[personIndex];\n\t\tif (newTeamSkills != teamSkills) {\n\t\t\t// include\n\t\t\tteam.addLast(personIndex);\n\t\t\tsmallestSufficientTeam(skillMasks, targetSkills, personIndex + 1, newTeamSkills, team, finalTeam, memo);\n\t\t\tteam.removeLast();\n\t\t\tmemo.put(key, team.size());\n\t\t}\n\t} else if (teamSkills == targetSkills) {\n\t\tfinalTeam.clear();\n\t\tfinalTeam.addAll(team);\n\t}\n}\n```\n***Please upvote if this helps***
['Java']