[C++] Top Down DP with Memoization
\nint dp[1 << 16][64];\nbool choice[1 << 16][64];\n\nclass Solution {\npublic:\n    int req_mask, m;\n    \n    vector<int> smallestSufficientTeam(vector<string
```\nint dp[1 << 16][64];\nbool choice[1 << 16][64];\n\nclass Solution {\npublic:\n    int req_mask, m;\n    \n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people_skills) {\n        int n = req_skills.size();\n        m = people_skills.size();\n        \n        // map each skill to a unique number\n        unordered_map<string, int> skills;\n        for (int i = 0; i < n; ++i)\n            skills[req_skills[i]] = i;\n        \n        // represent each person by a single bitmasked number (k\'th bit represents if a person has the k\'th skill or not)\n        vector<int> people;\n        for (auto &v: people_skills) {\n            int h = 0;\n            for (string &skill: v)\n                h |= 1 << skills[skill];\n            \n            people.push_back(h);\n        }\n        \n        // required set of skills mask\n        req_mask = (1 << n) - 1;\n        \n        memset(dp, -1, 1 << n + 8);\n        memset(choice, 0, 1 << n + 6);\n        \n        // modified dp\n        solve(people, 0, 0);\n        \n        // build the answer through the choice matrix (see the solve function first)\n        vector<int> ans;\n        for (int i = 0, mask = 0; i < m; ++i) {\n            // did we include the i\'th person?\n            if (choice[mask][i]) {\n                ans.push_back(i);\n                mask |= people[i];\n            }\n            \n            if (mask == req_mask)\n                break;\n        }\n        \n        return ans;\n    }\n    \n    // dp with memo\n    int solve(vector<int> &people, int i, int mask) {\n        if (mask == req_mask)\n            return 0;\n        if (i == m)\n            return 10000;\n        \n        int &ans = dp[mask][i];\n        if (ans != -1)\n            return ans;\n        \n        // include current person in the team\n        int ans1 = solve(people, i+1, mask | people[i]) + 1;\n        \n        // don\'t include\n        int ans2 = solve(people, i+1, mask);\n        \n        // did we include the current person to get the minimum result?\n        if (ans1 < ans2)\n            choice[mask][i] = 1;\n        \n        return ans = min(ans1, ans2);\n    }\n};\n```\n
['Dynamic Programming', 'Bitmask']