LeetCode 热题 100_括号生成（59_22_中等_C++）（递归（回溯））

题目描述：

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

输入输出样例：

示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2：
输入：n = 1
输出：[“()”]

提示：
1 <= n <= 8

题解：

解题思路：

思路一（递归（回溯））：

1、可以容易的想到递归树的结构，左子树为左括号’(‘，右子树为右括号’)‘，这样通过递归就可以构造出有效的括号组合。
有效的括号组合有几个条件：
① 最终左括号和右括号相等。
② 在构建有效括号时必定 : 左括号’(‘的数量 >= 右括号’)‘的数量。
③ 假设n对括号，则 ：左括号’(’ + 右括号’)’ =2n。
解决回溯问题，最好的方法还是先画出递归树，递归树如下图所示。

2、复杂度分析：
① 时间复杂度：O(m)，m为递归树中的节点数。
② 空间复杂度：O(n)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，最多递归 2n 层，因此空间复杂度为 O(n)。

代码实现（思路一（递归（回溯）））：

class Solution {

private:
    string path;               // 用于构建当前的括号路径
    vector<string> ans;        // 存储所有合法的括号组合

    // 回溯函数，递归生成括号组合
    void backtracking(int n, int n_left, int n_right) {
        // 如果左括号的数量小于右括号的数量，或者左括号数量大于n，直接返回
        if (n_left < n_right || n_left > n) return;

        // 如果当前路径已经包含2*n个括号（即一对完整的括号对），则是一个合法的组合
        if (path.size() == 2 * n) {
            ans.emplace_back(path);  // 将当前路径（括号组合）加入到答案中
            return;
        }

        // 尝试添加一个左括号
        path += '(';
        backtracking(n, n_left + 1, n_right);  // 递归调用，左括号数量加1
        path.pop_back();  // 回溯，撤销上一步的操作

        // 尝试添加一个右括号
        path += ')';
        backtracking(n, n_left, n_right + 1);  // 递归调用，右括号数量加1
        path.pop_back();  // 回溯，撤销上一步的操作
    }

public:
    // 主函数，用于生成括号组合
    vector<string> generateParenthesis(int n) {
        if (n <= 0) return {};  // 如果n小于等于0，则返回空集合（没有合法括号组合）
        ans.clear();  // 清空之前的结果
        path.clear();  // 清空当前路径
        backtracking(n, 0, 0);  // 调用回溯函数，初始时左右括号的数量都是0
        return ans;  // 返回所有合法的括号组合
    }
};

以思路一为例进行调试

#include<iostream>
#include <vector>
using namespace std;

class Solution {

private:
    string path;               // 用于构建当前的括号路径
    vector<string> ans;        // 存储所有合法的括号组合

    // 回溯函数，递归生成括号组合
    void backtracking(int n, int n_left, int n_right) {
        // 如果左括号的数量小于右括号的数量，或者左括号数量大于n，直接返回
        if (n_left < n_right || n_left > n) return;

        // 如果当前路径已经包含2*n个括号（即一对完整的括号对），则是一个合法的组合
        if (path.size() == 2 * n) {
            ans.emplace_back(path);  // 将当前路径（括号组合）加入到答案中
            return;
        }

        // 尝试添加一个左括号
        path += '(';
        backtracking(n, n_left + 1, n_right);  // 递归调用，左括号数量加1
        path.pop_back();  // 回溯，撤销上一步的操作

        // 尝试添加一个右括号
        path += ')';
        backtracking(n, n_left, n_right + 1);  // 递归调用，右括号数量加1
        path.pop_back();  // 回溯，撤销上一步的操作
    }

public:
    // 主函数，用于生成括号组合
    vector<string> generateParenthesis(int n) {
        if (n <= 0) return {};  // 如果n小于等于0，则返回空集合（没有合法括号组合）
        ans.clear();  // 清空之前的结果
        path.clear();  // 清空当前路径
        backtracking(n, 0, 0);  // 调用回溯函数，初始时左右括号的数量都是0
        return ans;  // 返回所有合法的括号组合
    }
};

int main(int argc, char const *argv[])
{
    int n = 2;  // 设置要生成括号组合的数量n，表示我们需要生成2对括号

    Solution s;  // 创建 Solution 类的对象 s
    vector<string> ans = s.generateParenthesis(n);  // 调用 generateParenthesis 函数，获取所有合法的括号组合

    cout << "[";  // 打印数组的开头，格式为 "["

    // 遍历 ans 中的每个括号组合并打印
    for (int i = 0; i < ans.size(); i++)
    {
        cout << "\"" << ans[i] << "\"";  // 打印当前的括号组合，使用双引号包裹
        if (i != ans.size() - 1)  // 如果不是最后一个元素
        {
            cout << ",";  // 则打印逗号分隔符
        }
    }

    cout << "]";  // 打印数组的结尾，格式为 "]"

    return 0;  // 返回0，表示程序执行成功
}

LeetCode 热题 100_括号生成（59_22)原题链接
欢迎大家和我沟通交流(✿◠‿◠)