Bit masking solution in python explained line by line in greatest depth possible
Here we represent every skill by one bit.\nExample:   req_skills=["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]\nsince no of r
Here we represent every skill by one bit.\nExample:   req_skills=["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]\nsince no of required skills are 3 we take 3 bits to represent them,\njava -> 001     (assuming if 1st bit is one then we have java as skill)\nnodejs -> 010   (assuming if 2nd bit is one then we have nodejs as skill)\nreactjs ->100 (assuming if 3rd bit is one then we have reactjs as skill)\n\nSo person 1 has skill of java i.e  p1 -> 001\nsimilarly p2 -> 010\nand p3 -> 110   (Since, p3 has both nodejs and reactjs as the skill)\n\nSo we have map of 000 to 111 where 111 denotes presence of all skills and 000 shows absence of all skills\nOur solution would be stored at 111 in the dp map.\n\nAlgorithm:\n1) For every skill provide a corresponding bit to it.\n2) Combine the skill formed by each person with all the skills in the map and update the map for that new skill\n\tonly if that skill is either not present or map has more people for that same skill than current people we are    getting.\n\tFor example suppose, map[5]=[1,2,3] that means to form 101 we need 3 persons but at later stage we get map[5]=[2,3] that means to form 101 now we only need person 2 and 3 so we update map then.\n3) After doing this step for all persons. We know that we have stored the optimal answer at dp[7(111)] (for 3 length skill array) or dp[15(1111)] (for 4 length skill array), etc... Which in general is dp[(1<<(len(people))-1].\n4) Return the answer stored at dp[(1<<(len(people))-1];\n\nCode for the same approach as stated above : \n````\nclass Solution(object):\n    def smallestSufficientTeam(self, req_skills, people):\n        map={}\n        for i in range(len(req_skills)): map[req_skills[i]]=i;\n        dp={0:[]}\n        for i in range(len(people)):\n            cskill=0\n            for skill in people[i]:\n                cskill |= (1<<(map[skill]))\n            for key,value in dp.items():\n                nskill = key | cskill\n                if((nskill not in dp) or len(dp[nskill])>len(value)+1):\n                   dp[nskill]=value+[i]\n        return dp[(1<<len(map))-1]\n````\n\t\nDry run with Example:\n Example 1: req_skills=["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]\n initially we map,\nmap =  { java : 0, nodejs : 1, reactjs: 2}\n Now for person 1 since he has java as the skill so we set bit at map[\'java\'] i.e 0, so p1\'s skill = 1 (001 in binary)\n For person   p2\'s skill = 2 (010 in binary)\n For person p3\'s skill = 6 (110 in binary) since the person 3 has nodejs and reactjs as skills which corresponds to 2nd and 1st bit respectively.\n \n Now starting from 0 we find the combined skill of that person with all other key present in the map, \n so we get dp[0]=[]\n   Now for person 0 (Skill value = 1(001 in binary))\n\t\t\t\t dp[1 | 0]=dp[1]=[0]\n\tNow for person 1   (Skill value = 2 (010 in binary))     [At each stage we perform bitwise or with all the keys already present in array]\n\t             dp[2 | 0]=dp[2]=[1]\n\t\t\t\t dp[2 | 1]=dp[3]=[0,1]\n\tFor person 2     (skill value =6  (110 in binary))\n\t             dp[6 | 0] = dp[6]=[2]\n\t\t\t\t dp[6 | 1] = dp[7] = [0,2]\n\t\t\t\t dp[6 | 2] = dp[6] = [1,2]  (Since we already have for dp[6] lesser length value hence we discard this)\n\t\t\t\t dp[6 | 3] = dp[7]=[0,1,2] (Since we already have for dp[7] lesser length value we discard this)\n\t\t\t\t \nFinally our answer is at dp[7] which is [0,2] which is the desired answer.\n\t\n  Tried to explain it in as simple terms as possible. Hopefully, readers get this solution  : -))\n
[]