DFS with pruning
Intuition\n Describe your first thoughts on how to solve this problem. \n- There are at most 16 skills, so we use bitmasks to represent each skill and skill com
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- There are at most 16 skills, so we use bitmasks to represent each skill and skill combinations.\n- For each person, we either hire or not hire, so we can use DFS to try all the states. This is fairly easy to write.\n- However, this is 2^M (M is the number of people) which is TLE. We need some way to trim the state tree.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- When adding a person, if adding this person does not expand the team\'s skills, then there is no need to add this person.\n- When ignore a person, if we know that the remaining people cannot cover the missing skills, then we can prune this branch.\n    - to do this we sort the people in decreasing order of number of skills they have (need to remember their original index); call this sorted people array peopleSkills.\n    - we then build a skillsCovered array that skillsCovered[i] represents the skills covered by peopleSkills[i:]\n    - therefore we can use skillsCovered[i] to check if the remaining people can fulfill the missing skills.\n\n\n# Code\nKotlin\n```\n    fun smallestSufficientTeam(req_skills: Array<String>, people: List<List<String>>): IntArray {\n        val map = req_skills.withIndex().associateBy({ it.value }, { it.index })\n        val target = 1.shl(req_skills.size) - 1\n        val peopleSkills = people.withIndex().map {\n            Pair(it.index, it.value.fold(0) { acc, s -> acc.or(1 shl map[s]!!) })\n        }.sortedBy { -people[it.first].size }\n        val skillsCovered = IntArray(peopleSkills.size).also {\n            var cover = 0\n            for ((i, v) in peopleSkills.withIndex().reversed()) {\n                cover = cover or v.second\n                it[i] = cover\n            }\n        }\n\n        var res = IntArray(peopleSkills.size) { it }\n\n        fun dfs(cur: Int, team: MutableList<Int>, covered: Int) {\n            if (covered == target) {\n                if (team.size < res.size) {\n                    res = team.toIntArray()\n                }\n                return\n            }\n            if (cur == peopleSkills.size) return\n            val newCovered = covered or peopleSkills[cur].second\n            if (newCovered != covered) {\n                // choose this person\n                team.add(peopleSkills[cur].first)\n                dfs(cur + 1, team, newCovered)\n                team.removeAt(team.lastIndex)\n\n            }\n            if (covered or skillsCovered.getOrElse(cur + 1) { 0 } == target) {\n                // ignore this person\n                dfs(cur + 1, team, covered)\n            }\n\n        }\n\n        dfs(0, mutableListOf(), 0)\n        return res\n    }\n```
['Kotlin']