[C] [100%] Top-down dynamic programming with explicit hash and bitmask;
Intuition\n\nIf we know how to find smallest teams for skillsets up to a given size, then, given a person, we may add that person to a team which covers a small
# Intuition\n\nIf we know how to find smallest teams for skillsets up to a given size, then, given a person, we may add that person to a team which covers a smaller skillset so that the larger team covers a larger skillset.\n\nIf we wish to cover a skillset with a team with a given person, we just need to look at which skills in the desired skillset that person does not cover, take the smallest team to cover those, and add that person to it. This gives us the smallest team with a given person to cover a given skillset. Letting the given person vary, we may obtain the overall smallest team.\n\n# Approach\n\nSkills are hashed with a closed hashing for simplicity.\n\nTeams (with at most 60 people, so there are at most $2^{60}$ distinct teams) are bitmasked as `unsigned long long` (from $0$ to $2^{64}-1$); Similarly, skillsets (at most 16) are bitmasked as `unsigned`.\n\nFor an empty skillset, an empty team is valid. For the other skillsets, we take a "full team" (every person), which certainly covers the skillset, and which will be improved recursively.\n\nFor a skillset $s$ and a person $P$, we let $s\'$ be the (strictly smaller) skillset consisting of skills in $s$ which are not covered by $P$. Take the optimal team $t\'$ to cover $s\'$ and add $P$ to it, obtaining a team $t$ which covers $s$. If $t$ is smaller than the previous team which covered $s$, we update it.\n\nThe optimal teams for given skillsets are stored in a DP array.\n\n# Complexity\n\nIf $m$ is the number of required skills and $n$ is the number of people:\n\n- Time complexity: $O(2^m\\cdot n)$, \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(2^m)$.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * Note: The returned array must be malloced, assume caller calls free().\n */\n\nsize_t hash_map(char * string , size_t hash_size) {\n    size_t out = 0;\n    for (size_t i=0 ; string[i] ; i++) {\n        out = ((out << 1) + (size_t)string[i] ) % hash_size;\n    }\n    return out;\n}\n\nsize_t get_idx( char * skill , char ** req_skills , size_t skills_hash_size , size_t * skills_hash ) {\n    size_t idx = hash_map( skill , skills_hash_size);\n    while ( strcmp(req_skills[skills_hash[idx]],skill) ) {\n        idx = (idx+1) % skills_hash_size;\n    }\n    return skills_hash[idx];\n}\n\nint number_of_bits(unsigned long long x) {\n    int n = 0;\n    while (x>0) {\n        n += x%2;\n        x>>=1;\n    }\n    return n;\n}\n\nint* smallestSufficientTeam(char ** req_skills, size_t req_skillsSize, char *** people, size_t peopleSize, int* peopleColSize, int* returnSize){\n    size_t skills_hash_size = 64;\n\n    size_t * skills_hash = calloc(skills_hash_size , sizeof(size_t));\n    {\n        size_t * skills_hash_occupied = calloc(skills_hash_size , sizeof(size_t));\n        for (size_t i=0 ; i<req_skillsSize ; i++) {\n            size_t idx = hash_map(req_skills[i] , skills_hash_size);\n            while (skills_hash_occupied[idx]) {\n                idx = (idx+1) % skills_hash_size;\n            }\n            skills_hash[idx] = i;\n            skills_hash_occupied[idx]=1;\n        }\n\n        free(skills_hash_occupied);\n    }\n\n    unsigned * skillsMaskOfPerson = calloc(peopleSize , sizeof(unsigned));\n    for (size_t i=0 ; i<peopleSize ; i++) {\n        for (size_t j=0 ; j<peopleColSize[i] ; j++) {\n            size_t idx = get_idx( people[i][j] , req_skills , skills_hash_size , skills_hash );\n            skillsMaskOfPerson[i] |= (1<<idx);\n        }\n        //printf("Bitmask of person %zu: %llu\\n", i , skillsMaskOfPerson[i]);\n    }\n\n    unsigned long long * dp = malloc((1<<req_skillsSize)*sizeof(unsigned long long));\n    for (size_t i=0 ; i< (1<<req_skillsSize) ; i++) {\n        dp[i] = ( ((unsigned long long)1)<<peopleSize)-1;\n        //printf("%llu ",dp[i]);\n    }\n\n    dp[0]=0;\n    \n    for (unsigned long long skillsMask = 0 ; skillsMask < (1<<req_skillsSize) ; skillsMask++) {\n        for (size_t i=0 ; i<peopleSize ; i++) {\n            unsigned long long smallerSkillsMask = skillsMask & (~skillsMaskOfPerson[i]);\n            if (smallerSkillsMask != skillsMask) {\n                unsigned long long peopleMask = dp[smallerSkillsMask] | (((unsigned long long)1)<<i);\n                if (number_of_bits(peopleMask) < number_of_bits(dp[skillsMask])) {\n                    dp[skillsMask] = peopleMask;\n                } \n            }\n        }\n    }\n\n    // dp[2^m-1] has the bitmask of the people we want\n\n    unsigned long long output_bitmask = dp[ (1<<req_skillsSize) - 1];\n    *returnSize = number_of_bits(output_bitmask);\n    int * output = malloc((*returnSize)*sizeof(int));\n    size_t index = 0;\n    for (size_t i=0 ; output_bitmask > 0 ; i++) {\n        if (output_bitmask %2) {\n            output[index++] = i;\n        }\n        output_bitmask>>=1;\n    }\n\n    return output;\n}\n```\n\n# Results\n\n![image.png](https://assets.leetcode.com/users/images/bf813eed-4926-49db-93e8-e59fe0d09d71_1689543093.1993694.png)\n
['Hash Table', 'Dynamic Programming', 'Bit Manipulation', 'C', 'Bitmask']