每日两题 / 78. 子集 && 17. 电话号码的字母组合（LeetCode热题100）

78. 子集 - 力扣（LeetCode）

通过二进制数的方式，若第k位为1，表示最终的集合中存在nums[k]
只要遍历所有可能的二进制数即可

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < (1 << n); ++ i)
        {
            vector<int> a;
            for (int k = 0; k < n; ++ k)
                if ((i >> k) & 1)
                    a.push_back(nums[k]);
            ans.push_back(a);
        }
        return ans;
    }
};

17. 电话号码的字母组合 - 力扣（LeetCode）

先建立数字与字符串之间的映射，接着dfs每个数字
每次取数字对应字符串中的一个字符加入可能的答案
当答案长度等于digits的长度，将可能的答案保存

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        unordered_map<char, string> mp;
        mp['2'] = "abc";
        mp['3'] = "def";
        mp['4'] = "ghi";
        mp['5'] = "jkl";
        mp['6'] = "mno";
        mp['7'] = "pqrs";
        mp['8'] = "tuv";
        mp['9'] = "wxyz";
        function<void(int, string&)> dfs = [&](int k, string &s){
            if (s.size() == digits.size())
            {
                ans.push_back(s);
                return;
            }
            for (auto t : mp[digits[k]])
            {
                s += t;
                dfs(k + 1, s);
                s.pop_back();
            }
        };
        
        if (digits.size() == 0) return ans;
        string ss; dfs(0, ss);
        return ans;
    }
};