Rust | Memoization, bitsets
Approach\nWe will find/memoize a mapping of subsets of skills to minimal subsets of people. For any given subset of skills, we will select one skill and iterate
# Approach\nWe will find/memoize a mapping of subsets of skills to minimal subsets of people. For any given subset of skills, we will select one skill and iterate through people that implement it; particular person\'s other skills will be subtracted from the necessary skill set, and recursion will be applied. Of resulting sets of people, the one with the minimal size will be selected.\n\n# Complexity\n- Time complexity: $O\\bigl(2^n \\cdot (n + m)\\bigr)$, where $n$ is the number of skills and $m$ is the number of people.\n\n- Space complexity: $O\\bigl(2^n \\cdot (n + m)\\bigr)$.\n\nUsing bitsets for skill sets and people sets appears to make this solution rather efficient (1ms, 2.2Mb). Replacing `HashMap` as cache with `Vec` improves speed, but consumes much more memory.\n\n# Code\n```\npub mod bitset {\n\n#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]\npub struct BitSet<C>(C);\n\nmacro_rules! impl_bitset { ($T:ty) => {\n    impl BitSet<$T> {\n        #[inline]\n        pub fn empty() -> Self {\n            Self(0)\n        }\n        #[inline]\n        pub fn full(size: u32) -> Self {\n            if size == <$T>::BITS {\n                Self(!0)\n            } else {\n                Self(<$T>::checked_shl(1, size).unwrap() - 1)\n            }\n        }\n        #[inline]\n        pub fn contains(&self, index: u32) -> bool {\n            self.0 & (<$T>::checked_shl(1, index).unwrap()) > 0\n        }\n        #[inline]\n        pub fn is_subset(&self, other: &Self) -> bool {\n            self.0 & other.0 == self.0\n        }\n        #[inline]\n        pub fn min(&self) -> Option<u32> {\n            match self.0.trailing_zeros() {\n                <$T>::BITS => None,\n                index => Some(index),\n            }\n        }\n        #[inline]\n        pub fn with(&self, index: u32) -> Self {\n            Self(self.0 | <$T>::checked_shl(1, index).unwrap())\n        }\n        #[inline]\n        pub fn add(&mut self, index: u32) -> () {\n            *self = self.with(index);\n        }\n        #[inline]\n        pub fn without(&self, index: u32) -> Self {\n            Self(self.0 - (self.0 & <$T>::checked_shl(1, index).unwrap()))\n        }\n        #[inline]\n        pub fn without_set(&self, other: &Self) -> Self {\n            Self(self.0 - (self.0 & other.0))\n        }\n        #[inline]\n        pub fn remove(&mut self, index: u32) -> () {\n            *self = self.without(index);\n        }\n        #[inline]\n        pub fn count(&self) -> u32 {\n            self.0.count_ones()\n        }\n    }\n    impl Iterator for BitSet<$T> {\n        type Item = u32;\n        #[inline]\n        fn next(&mut self) -> Option<u32> {\n            match BitSet::<$T>::min(&self) {\n                None => None,\n                Some(index) => {\n                    self.0 -= unsafe {\n                        // SAFETY: .min() always returns a value in range\n                        <$T>::checked_shl(1, index).unwrap_unchecked()\n                    };\n                    Some(index)\n                },\n            }\n        }\n    }\n    impl std::iter::FromIterator<u32> for BitSet<$T> {\n        #[inline]\n        fn from_iter<T: IntoIterator<Item=u32>>(iter: T) -> BitSet<$T> {\n            let mut set = Self::empty();\n            for value in iter {\n                set.add(value);\n            }\n            set\n        }\n    }\n}; }\n\nimpl_bitset!(u16);\nimpl_bitset!(u64);\n\n} // mod bitset\n\n\nuse std::collections::HashMap;\n\nuse bitset::BitSet;\ntype SkillSet = BitSet<u16>;\ntype PeopleSet = BitSet<u64>;\n\nimpl Solution {\n\n    pub fn smallest_sufficient_team(\n        req_skills: Vec<String>,\n        people: Vec<Vec<String>>,\n    ) -> Vec<i32> {\n        let n = req_skills.len() as u32;\n        let m = people.len() as u32;\n        let people_skills: Vec<SkillSet> = {\n            let rev_skills = req_skills.into_iter().enumerate()\n                .map(|(i, name)| (name, i as u32))\n                .collect::<std::collections::HashMap<_,_>>();\n            people.into_iter().map( |person_skills|\n                person_skills.into_iter()\n                    .map(|name| rev_skills[&name])\n                    .collect()\n            ).collect()\n        };\n        let people_by_skill: Vec<PeopleSet> = (0..n).map(|skill| {\n            people_skills.iter().enumerate().filter_map( |(i, skills)|\n                if !skills.contains(skill) {\n                    None\n                } else {\n                    Some(i as u32)\n                }\n            ).collect()\n        }).collect();\n        Solution::smallest_sufficient_team_recurse(\n            &mut HashMap::new(),\n            &people_skills, &people_by_skill,\n            SkillSet::full(n),\n        ).map(|x| x as i32).collect::<Vec<_>>()\n    }\n\n    pub fn smallest_sufficient_team_recurse(\n        cache: &mut HashMap<SkillSet,PeopleSet>,\n        people_skills: &Vec<SkillSet>,\n        people_by_skill: &Vec<PeopleSet>,\n        skills: SkillSet,\n    ) -> PeopleSet {\n        match cache.get(&skills) {\n            None => (),\n            Some(&team) => return team,\n        }\n        let team = match skills.min() {\n            None => PeopleSet::empty(),\n            Some(skill) => people_by_skill[skill as usize]\n                .map( |i|\n                    Solution::smallest_sufficient_team_recurse(\n                        cache, people_skills, people_by_skill,\n                        skills.without_set(&people_skills[i as usize]),\n                    ).with(i)\n                )\n                .min_by_key(|team| team.count())\n                .expect("someone should have this skill"),\n        };\n        cache.insert(skills, team);\n        return team;\n    }\n\n}\n```
['Rust']