板子是主循环啥也不干，只指明下标，dfs里面两种情况，选或不选。

216. 组合总和 III

class Solution {
public:
    vector<vector<int>> res;
    int n, k;
    vector<vector<int>> combinationSum3(int k_, int n_) {
        n = n_, k = k_;
        vector<int> tmp;
        dfs(tmp, 1, 0);
        return res;
    }

    // tmp数组  u下标  sum总和
    void dfs(vector<int>& tmp, int u, int sum)
    {
        if (sum == n && tmp.size() == k)
        {
            res.push_back(tmp);
            return;
        }
        if (sum > n || tmp.size() > k)
            return;
        if (u > 9) return;

        dfs(tmp, u + 1, sum);
        tmp.push_back(u);
        dfs(tmp, u + 1, sum + u);
        tmp.pop_back();
    }
};

17. 电话号码的字母组合

class Solution {
public:
    string digits;
    vector<string> res;
    unordered_map<char, vector<char>> umap;
    vector<string> letterCombinations(string digits_) {
        digits = digits_;
        init(); //初始化键盘
        if (digits.size() == 0) return {};
        string tmp;
        dfs(tmp, 0);
        return res;
    }

    void dfs(string s, int u)
    {
        if (u == digits.size())
        {
            res.push_back(s);
            return;
        }
        for(auto ch : umap[digits[u]])
        {
            string tmp = s + ch;
            dfs(tmp, u + 1);
        }
    }

    void init()
    {
        umap['2'] = {'a', 'b', 'c'};
        umap['3'] = {'d', 'e', 'f'};
        umap['4'] = {'g', 'h', 'i'};
        umap['5'] = {'j', 'k', 'l'};
        umap['6'] = {'m', 'n', 'o'};
        umap['7'] = {'p', 'q', 'r', 's'};
        umap['8'] = {'t', 'u', 'v'};
        umap['9'] = {'w', 'x', 'y', 'z'};
    }
};