leetcode22：括号生成

题目链接

leetcode

题目描述

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

C++ 代码

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

/*
    回溯法，深度优先搜索

    每次可以放置左括号的条件：
        剩余左括号的数目大于 0。
    每次可以放置右括号的条件：
        剩余右括号的数目大于 0，并且大于左括号的数目。

    时间复杂度：O(4^n/sqrt(n))
        每个括号组合，都有两个选择：添加左括号或添加右括号。
        在最坏的情况下，可能需要生成所有 2^n 个括号组合，然后筛选出有效的组合。
        实际上有效的组合远小于这个数，约等于卡特兰数，其增长速度为 O(4^n/sqrt(n))。
    空间复杂度：O(n)  
        除了答案数组之外，所需要的空间取决于递归栈的深度，
        每一层递归函数需要空间 O(1)，最多递归 2n 层。
*/
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;    // 记录所有合法的括号组合
        string path;           // 回溯过程中的路径
        dfs(res, path, n, n);  // 可用的左括号和右括号的数量初始化为 n
        
        return res;
    }

    void dfs(vector<string>& res, string path, int lc, int rc) {
        // 结束条件：剩余左括号和右括号的数量等于0
        if (lc == 0 && rc == 0) {
            res.push_back(path);
        }

        if (lc > 0) {
            dfs(res, path+'(', lc-1, rc);
        }
        if (rc > 0 && lc < rc) {
            dfs(res, path+')', lc, rc-1);
        }
    }
};

/*
    题目可以改写为：
        2n 个位置，每个位置可以放置 '(' 或 ')'，
        组成的所有括号组合中，有多少个是合法的？
    这是典型的回溯算法，暴力穷举即可。

    为了减少不必要的穷举，合法的括号组合满足性质：
        1.左括号的数量不超过 n
        2.右括号的数量不超过左括号
	从左向右计算，最后左右括号的数量相等，说明这个括号组合是合法的。
*/
class Solution_1 {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;    // 记录所有合法的括号组合
        string path;           // 回溯过程中的路径
        dfs(res, path, n, n);  // 可用的左括号和右括号的数量初始化为 n

        return res;
    }

    void dfs(vector<string>& res, string& path, int left, int right) {
        // 结束条件：剩余左括号的数量大于右括号
        if (left > right) {
            return;
        }
        // 结束条件：剩余左括号或者右括号的数量小于0
        if (left < 0 || right < 0) {
            return;
        }
        // 结束条件：剩余左括号和右括号的数量等于0
        if (left == 0 && right == 0) {
            res.push_back(path);
            return;
        }

        // 尝试放一个左括号
        path.push_back('('); // 选择
        dfs(res, path, left-1, right);
        path.pop_back();     // 撤消选择：回溯

        // 尝试放一个右括号
        path.push_back(')'); // 选择
        dfs(res, path, left, right-1);
        path.pop_back();     // 撤消选择：回溯
    }
};

// 辅助函数：打印二维数组
void printArray(const vector<string>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "\"" << nums[i] << "\"";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<int> n_cases = {3, 1};

    for (int n : n_cases) {
        vector<string> result = solution.generateParenthesis(n);

        cout << "Input: n = " << n << endl;
        cout << "Output: ";
        printArray(result);
    }

    return 0;
}