JS | BFS/DFS
Intuition\n Describe your first thoughts on how to solve this problem. \nBoth BFS/DFS can be used to more or less brute force this problem, with memoization.\n\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBoth BFS/DFS can be used to more or less brute force this problem, with memoization.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can essentially treat each person as a vertex in a connected graph. That means we can jump from any person to any person, and when we have accumulated a group of people which satisfies the requirements, we return that group. We repeat until we find the smallest group, going through all possible paths. Because the input sizes preclude complete brute force, we add a memoization array to make sure we don\'t go down a path which satisfies a set of skills that was already satisfied with fewer people.\n\nBFS works, but turns out to be a pretty poor performer (as implemented here), due to the fact that we need to reconstruct the path we took to reach the smallest sufficient team. With DFS, we can just store a single global result array, and just replace it whenever we find a better answer.\n\n# Code\n## DFS\n```js\n/**\n * @param {string[]} req_skills\n * @param {string[][]} people\n * @return {number[]}\n */\nvar smallestSufficientTeam = function(req_skills, people) {\n    let skillCount = req_skills.length;\n\n    //since there\'s only 16 skills max, create a bit string where each skill corresponds to a bit in an integer.\n    //we start by choosing which skill should go to which index in the int.\n    //in this case, we just go in the order of appearance in the requirements array.\n    let reqByName = new Map();\n    for(let i = 0; i < req_skills.length; ++i) {\n        reqByName.set(req_skills[i], 1<<i);\n    }\n    req_skills = null;\n\n    //take the skills for each person and turn it into a bit string (int)\n    people = people.map(x => {\n        let num = 0;\n        for(let skill of x) {\n            num |= reqByName.get(skill);\n        }\n        return num;\n    });\n    reqByName = null;\n\n    //target is 2^skillCount-1 (each bit set to 1)\n    let target = (1<<(skillCount))-1;\n    //we allocate a DP array with every possible bit string * each position in the people array.\n    let dp = new Uint8Array(people.length * target);\n\n    //global state to hold the final result\n    let state = {ans: null};\n\n    dfs(dp, target, 0, people, 0, [], state);\n\n    return state.ans;\n};\n\nfunction dfs(dp, target, bitStr, people, l, ans, state) {\n    if(bitStr === target) {\n        if(!state.ans || state.ans.length > ans.length) {\n            state.ans = ans.slice(0);\n        }\n        return;\n    }\n    if(l >= people.length) {\n        return;\n    }\n\n    //we\'re on the wrong track if the ans is longer than a result we already found\n    if(state.ans && ans.length >= state.ans.length) {\n        return;//stop considering this branch\n    }\n\n    let dpIdx = (people.length * bitStr) + l;\n    if(dp[dpIdx] > 0 && (dp[dpIdx]-1) <= ans.length) {\n        return;\n    }\n\n    //recurse without using this person\n    dfs(dp, target, bitStr, people, l+1, ans, state);\n\n    if((people[l]&bitStr) !== people[l]) {\n        ans.push(l);\n        //recurse using this person\n        dfs(dp, target, bitStr|people[l], people, l+1, ans, state)+1;\n        ans.pop(l);\n    }\n\n    //we\'ve now considered this index & input bitStr, for a given answer prefix length.\n    //Only go down this path if we reach this position with a shorter prefix.\n    dp[dpIdx] = ans.length+1;//__prefix size__\n}\n\n```\n\nBeats 100%/100%\n\n\n## BFS \n```js\n/**\n * @param {string[]} req_skills\n * @param {string[][]} people\n * @return {number[]}\n */\nvar smallestSufficientTeam = function(req_skills, people) {\n    //same setup as above\n    let skillCount = req_skills.length;\n    let target = (1<<(skillCount))-1;\n\n    let reqByName = new Map();\n\n    for(let i = 0; i < req_skills.length; ++i) {\n        reqByName.set(req_skills[i], 1<<i);\n    }\n    req_skills = null;\n\n\n    let foundTarget = null;\n    people = people.map((x, idx) => {\n        let num = 0;\n        for(let skill of x) {\n            num |= reqByName.get(skill);\n        }\n        if(num === target) { foundTarget = idx; }\n        return num;\n    });\n    reqByName = null;\n\n    if(foundTarget !== null) { return [foundTarget]; }\n\n    //since we\'re doing a breadth first search, if we\'ve \n    //found a bit string before, that means that we got there\n    //with a shorter path already. Therefore, if seen, skip.\n    //we store the previous index and the previous person ID\n    //in the seen array, so that we can reconstruct the path through\n    //the people array we took.\n    //[PREVIOUS_SEEN_IDX,PERSON_IDX][]\n    let seen = new Array(target);\n\n    //build a q with all the people, \n    //[BIT_STRING,PREV_SEEN_IDX,PREV_PERSON_IDX][]\n    let q = people.map((x,idx)=>[x,null,idx]), q2 = [];\n    while(q.length || q2.length) {\n        if(!q.length) {\n            [q, q2] = [q2, q];\n        }\n        let [cur, source, sourceIdx] = q.pop();\n        if(cur in seen) {\n            continue;\n        }\n        seen[cur] = [source, sourceIdx];\n\n        //since we have a connected graph, look at every other person\n        for(let i = 0; i < people.length; ++i) {\n            let next = people[i]|cur;\n            if(next === target) { \n                let ret = []\n                ret.push(i);\n                //treat the seen array as a linked list and reconstruct\n                //the path we took\n                while(true) {\n                    ret.push(sourceIdx)\n                    let tmp = source;\n                    if(!seen[tmp]) { break; }\n                    [source, sourceIdx] = seen[tmp];\n                }\n                return ret;\n            }\n            if(next !== cur && !(next in seen)) {\n                q2.push([next, cur, i]);\n            }\n        }\n    }\n};\n\n```\n\nThis approach is about 4x slower, and uses more than double the memory. Some performance improvements could be made by storing things more intelligently to eliminate some of the pointer chasing, but I don\'t think it\'ll ever be faster than a DFS for this problem.
['JavaScript']