【回溯+剪枝】电话号码的字母组合 括号生成

17. 电话号码的字母组合

17. 电话号码的字母组合

​ 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

​ 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

解题思路：回溯 + 哈希表

​ 这道题其实就是暴力搜索，要遍历所有的叶子节点拿到所有的结果。其中因为每个位置可选择的字符与其他位置并不冲突，因此不需要标记已经出现的字符，只需要将每个数字对应的字符依次填入字符串中进行递归，然后在回溯时候进行撤销之前的填入操作即可。

​ 只不过为了快速找到当前数字对应的字母组合，我们需要在递归之前我们需要定义一个 哈希表 hash，记录 2~9 各自对应的字符。（但实际上在实现的时候，为了方便我们可以直接给出 10 个元素大小的字符串数组即可，其中 0 和 1 都是空串！

​ 接下来的步骤其实就和全排列问题是类似的，要下标 0 处开始遍历所有的结果！只不过要注意的是递归函数出口的细节，因为有可能这道题传入的手机号码是空串，此时题目要求如果是空串的话，返回的结果是什么都没有，所以我们就需要在递归函数出口处判断一下，如果电话号码不是空串再进行添加结果集操作！

class Solution {
private:
    string hash[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ret; // 存放结果集
    string path;        // 存放路径上的字符
public:
    vector<string> letterCombinations(string digits) {
        dfs(digits, 0);
        return ret;
    }

    void dfs(string& digits, int index)
    {
        // 递归函数出口
        if(index == digits.size())
        {
            if(digits.size() > 0)
                ret.push_back(path);
            return;
        }

        string tmp = hash[digits[index] - '0']; // 先拿到当前数字对应的字符串
        for(int i = 0; i < tmp.size(); ++i) 
        {
            // 处理当前节点
            path.push_back(tmp[i]);

            // 先递归处理该节点下面的其它路径
            dfs(digits, index + 1);

            // 进行回溯处理
            path.pop_back();
        }
    }
};

22. 括号生成

22. 括号生成

​ 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

解题思路：回溯 + 剪枝

​ 这道题其实就是一个暴力搜索，我们在搜索之前还需要知道有效的括号组合的要求：

• 左括号数量 = 右括号数量 = n。
• 在遍历途中，保证三个小要求：
  1. 左括号数量不超过 n。
  2. 右括号数量不超过 n。
  3. 左括号数量一定要大于等于右括号数量，才能保证右括号至少有一个左括号与之匹配。

​ 知道了有效的括号组合要求之后，就是开始构建一棵决策树，其实就是每次看选左括号还是右括号，然后选完之后再递归继续选，直到最后符合上述的要求为止，决策树如下图所示，以 n=2 为例：

​ 所以为了达到剪枝的效果，我们需要有一个 left 和一个 right 变量，来记录当前左括号和右括号的数量，如果不符合上述的要求的话直接就剪枝了！

​ 然后在递归的时候，如果选择的是左括号的话，则让 left+1，如果选择的是右括号的话则让 right+1 去递归，这里我们将这两个变量设为局部变量，这样子每一层的 left 和 right 就不会互相干扰，就不用在回溯的时候进行处理！

​ 剩下的细节都是一样的，具体参考代码！

class Solution {
private:
    vector<string> ret; // 存放结果集
    string path;        // 存放当前路径的字符串
public:
    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0);
        return ret;
    }

    void dfs(int n, int left, int right)
    {
        // 递归函数出口
        if(left > n || right > n || right > left)
            return;
        
        // 如果满足括号数量则添加结果集并且返回
        if(left == n && right == n)
        {
            ret.push_back(path);
            return;
        }

        string tmp = "()";
        for(int i = 0; i < tmp.size(); ++i)
        {
            // 处理当前节点
            path.push_back(tmp[i]);

            // 递归后面的路径
            if(tmp[i] == '(')
                dfs(n, left + 1, right);
            else 
                dfs(n, left, right + 1);
            
            // 回溯处理
            path.pop_back();
        }
    }
};