自学内容网 自学内容网
自学内容网 > 正文

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

🕗 发布于 2024-11-18 13:02 leetcode  算法  javascript  

题目

数字 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();：在递归调用返回后，移除最后一个字符（即刚刚添加的右括号），以便尝试其他可能的组合。

原文地址：https://blog.csdn.net/wxtg1921/article/details/143839794

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024