力扣题目解析--括号生成

题目

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

代码展示 

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string sb;
        vector<string> res;
        dfs(n, sb, res, 0, 0);
        return res;
    }

private:
    void dfs(int n, string& sb, vector<string>& res, int left, int right) {
        if (left == n && right == n) {
            res.push_back(sb);
        }
        if (left < n) {
            sb += "(";
            dfs(n, sb, res, left + 1, right);
            sb.pop_back();
        }
        if (right < left) {
            sb += ")";
            dfs(n, sb, res, left, right + 1);
            sb.pop_back();
        }
    }
};

写者心得 

这段代码使用的是回溯的思想，代码是通过学习力扣题解里边儿的思想在改进过来的，这种思想其实和双指针是一脉相承的

这个题目它的逻辑过程是这个样子的：

n=0:''
n=1:   排列组合
        (0):
            ('')----> ()
n=2:  排列组合
       (0)+1: 
            ('')+()----> ()()
       (1)+0: 
            (())+''----->(())
n=3: 排列组合
       (0)+2: 
            ('')+()() ----> ()()()
            ('')+(())----->()(())
       (1)+1:
            (())+()------> (())()
       (2)+0:
            (()())+'' ----> (()())
            ((()))+''----->((()))
n=4: 排列组合
       (0)+3:
            ('')+()()()--->()()()()
            ('')+()(())--->()()(())
            ('')+ (())()--->()(())()
            ('')+(()())--->()(()())
            ('')+((()))--->()((()))
       (1)+2:
            (())+()()--->(())()()
            (())+(())--->(())(())
       (2)+1:
            (()())+()---->(()())()
            ((()))+()---->((()))()
       (3)+0:
            (()()())+''---->(()()())
            (()(()))+''---->(()(()))
            ((())())+''---->((())())
            ((()()))+''---->((()()))
            (((())))+''---->(((())))

调试过程解析

1. 初始化和首次调用

• generateParenthesis(int n):
  • 初始化一个空字符串 sb 和一个空的字符串向量 res。
  • 调用 dfs(n, sb, res, 0, 0)，开始递归搜索。

2. 第一次递归调用 dfs(n, sb, res, 0, 0)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "", res = [], left = 0, right = 0
  • 检查条件 left == n && right == n：不满足，继续。
  • 检查条件 left < n：满足，left = 0 < 2。
  • 更新 sb += "("，sb = "("。
  • 递归调用 dfs(n, sb, res, left + 1, right)，即 dfs(2, "(", res, 1, 0)。

3. 第二次递归调用 dfs(2, "(", res, 1, 0)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "(", res = [], left = 1, right = 0`
  • 检查条件 left == n && right == n：不满足，继续。
  • 检查条件 left < n：满足，left = 1 < 2。
  • 更新 sb += "("，sb = "(("。
  • 递归调用 dfs(n, sb, res, left + 1, right)，即 dfs(2, "((", res, 2, 0)。

4. 第三次递归调用 dfs(2, "((", res, 2, 0)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "((", res = [], left = 2, right = 0
  • 检查条件 left == n && right == n：不满足，继续。
  • 检查条件 left < n：不满足，left = 2。
  • 检查条件 right < left：满足，right = 0 < 2。
  • 更新 sb += ")"，sb = "(()"。
  • 递归调用 dfs(n, sb, res, left, right + 1)，即 dfs(2, "(()", res, 2, 1)。

5. 第四次递归调用 dfs(2, "(()", res, 2, 1)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "(()", res = [], left = 2, right = 1
  • 检查条件 left == n && right == n：不满足，继续。
  • 检查条件 left < n：不满足，left = 2。
  • 检查条件 right < left：满足，right = 1 < 2。
  • 更新 sb += ")"，sb = "(())"。
  • 递归调用 dfs(n, sb, res, left, right + 1)，即 dfs(2, "(())", res, 2, 2)。

6. 第五次递归调用 dfs(2, "(())", res, 2, 2)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "(())", res = [], left = 2, right = 2
  • 检查条件 left == n && right == n：满足，left = 2 且 right = 2。
  • 将 sb 添加到 res 中，res = ["(())"]。
  • 返回上一级递归调用。

7. 返回到第四次递归调用 dfs(2, "(()", res, 2, 1)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "(()", res = ["(())"], left = 2, right = 1
  • 执行 sb.pop_back()，sb = "(()"。
  • 返回上一级递归调用。

8. 返回到第三次递归调用 dfs(2, "((", res, 2, 0)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "((", res = ["(())"], left = 2, right = 0
  • 执行 sb.pop_back()，sb = "("。
  • 返回上一级递归调用。

9. 返回到第二次递归调用 dfs(2, "(", res, 1, 0)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "(", res = ["(())"], left = 1, right = 0
  • 检查条件 right < left：满足，right = 0 < 1。
  • 更新 sb += ")"，sb = "()"。
  • 递归调用 dfs(n, sb, res, left, right + 1)，即 dfs(2, "()", res, 1, 1)。

10. 第六次递归调用 dfs(2, "()", res, 1, 1)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "()", res = ["(())"], left = 1, right = 1
  • 检查条件 left == n && right == n：不满足，继续。
  • 检查条件 left < n：满足，left = 1 < 2。
  • 更新 sb += "("，sb = "()("。
  • 递归调用 dfs(n, sb, res, left + 1, right)，即 dfs(2, "()(", res, 2, 1)。

11. 第七次递归调用 dfs(2, "()(", res, 2, 1)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "()(", res = ["(())"], left = 2, right = 1
  • 检查条件 left == n && right == n：不满足，继续。
  • 检查条件 left < n：不满足，left = 2。
  • 检查条件 right < left：满足，right = 1 < 2。
  • 更新 sb += ")"，sb = "()(())"。
  • 递归调用 dfs(n, sb, res, left, right + 1)，即 dfs(2, "()(())", res, 2, 2)。

12. 第八次递归调用 dfs(2, "()(())", res, 2, 2)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "()(())", res = ["(())"], left = 2, right = 2
  • 检查条件 left == n && right == n：满足，left = 2 且 right = 2。
  • 将 sb 添加到 res 中，res = ["(())", "()()"]。
  • 返回上一级递归调用。

13. 返回到第七次递归调用 dfs(2, "()(", res, 2, 1)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "()(", res = ["(())", "()()"], left = 2, right = 1
  • 执行 sb.pop_back()，sb = "()("。
  • 返回上一级递归调用。

14. 返回到第六次递归调用 dfs(2, "()", res, 1, 1)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "()", res = ["(())", "()()"], left = 1, right = 1
  • 执行 sb.pop_back()，sb = "()"。
  • 返回上一级递归调用。

15. 返回到第二次递归调用 dfs(2, "(", res, 1, 0)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "()", res = ["(())", "()()"], left = 1, right = 0
  • 执行 sb.pop_back()，sb = "("。
  • 返回上一级递归调用。

16. 返回到第一次递归调用 dfs(2, "", res, 0, 0)

• dfs(int n, string& sb, vector<string>& res, int left, int right):
  • 参数：n = 2, sb = "(", res = ["(())", "()()"], left = 0, right = 0
  • 执行 sb.pop_back()，sb = ""。
  • 返回上一级调用。

代码的逐行解释 

vector<string> generateParenthesis(int n) {
        string sb;
        vector<string> res;
        dfs(n, sb, res, 0, 0);
        return res;
    }

• vector<string> generateParenthesis(int n)：定义了 generateParenthesis 函数，它接受一个整数 n 作为参数，并返回一个 vector<string> 类型的对象，该对象包含所有合法的括号组合。
• string sb;：初始化一个空字符串 sb，用于构建当前正在生成的括号组合。
• vector<string> res;：初始化一个空的字符串向量 res，用于存储所有合法的括号组合。
• dfs(n, sb, res, 0, 0);：调用私有成员函数 dfs，开始深度优先搜索。n 是目标括号对的数量，sb 是当前正在构建的字符串，res 是存储结果的向量，0, 0 分别表示当前已经添加的左括号和右括号的数量。
• return res;：返回存储所有合法括号组合的向量 res。

private:

这行指定了接下来定义的成员函数或变量是私有的（private），意味着它们只能在类的内部被访问

    void dfs(int n, string& sb, vector<string>& res, int left, int right) {

• void dfs(int n, string& sb, vector<string>& res, int left, int right)：定义了私有成员函数 dfs，它接受五个参数：
  • int n：目标括号对的数量。
  • string& sb：引用传递的当前正在构建的字符串。
  • vector<string>& res：引用传递的存储结果的向量。
  • int left：当前已经添加的左括号的数量。
  • int right：当前已经添加的右括号的数量。

        if (left == n && right == n) {
            res.push_back(sb);
        }

• if (left == n && right == n)：检查当前已经添加的左括号和右括号的数量是否都达到了目标数量 n。
• res.push_back(sb);：如果条件满足，说明当前构建的字符串 sb 是一个合法的括号组合，将其添加到结果向量 res 中。

        if (left < n) {
            sb += "(";
            dfs(n, sb, res, left + 1, right);
            sb.pop_back();
        }

• if (left < n)：检查当前已经添加的左括号数量是否小于目标数量 n。
• sb += "(";：如果条件满足，向当前字符串 sb 添加一个左括号。
• dfs(n, sb, res, left + 1, right);：递归调用 dfs 函数，增加左括号的数量。
• sb.pop_back();：在递归调用返回后，移除最后一个字符（即刚刚添加的左括号），以便尝试其他可能的组合。

        if (right < left) {
            sb += ")";
            dfs(n, sb, res, left, right + 1);
            sb.pop_back();
        }

• if (right < left)：检查当前已经添加的右括号数量是否小于左括号的数量。这个条件确保了不会生成非法的括号组合（即右括号的数量不能超过左括号的数量）。
• sb += ")";：如果条件满足，向当前字符串 sb 添加一个右括号。
• dfs(n, sb, res, left, right + 1);：递归调用 dfs 函数，增加右括号的数量。
• sb.pop_back();：在递归调用返回后，移除最后一个字符（即刚刚添加的右括号），以便尝试其他可能的组合。