题目链接

https://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca?tpId=188&&tqId=38655&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking

题目描述

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。 例如，给出n=3，解集为： "((()))", "(()())", "(())()", "()()()", "()(())",

思路分析

  1. 方法一 递归求解
  • 分析：利用递归求解此题的核心思路就是将所有的括号可能都列举一遍，然后对每一种可能判断其是否为合法的括号序列。
  • 判断序列是否为合法序列的方法： 通过堆栈判断，举例说明： ()()((())) ---合法序列 (((()))) ---合法序列 ()(((( ---非法序列 )() ---非法序列 通过观察可以发现任意合法的序列当其出现(时，一定会有相同数量的)在其之后出现，根据这一性质我们可以利用栈来模拟，我们遍历一遍当前序列，若遇到(，则将其入栈，若遇到),则将栈顶元素删除，如果序列合法，则最终栈的元素个数一定为0，反之，则会出现栈最终不为空或者提前不够用的情况。

参考代码

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    bool check(string str) {        //检查括号序列的合法性
        stack<char> stk;
        for(int i = 0; i < str.size(); i ++ ) {
            if(str[i] == '(') stk.push('(');    //遇到'('入栈
            else {
                if(stk.size() > 0) stk.pop();   //遇到')'出栈
                else return false;              //非法序列直接退出
            }
        }
        if(stk.size() == 0) return true;
        else return false;
    }
    void mygen(int num, string str, vector<string>& ans, int cnt) {    
    //递归枚举所有序列情况
        if(cnt == num + 1) {
            if(check(str)) ans.push_back(str);
            return ;
        }
        str = str + '(';    //当前位置为'('
        mygen(num, str, ans, cnt + 1);  //递归下一个位置
        str.pop_back();     //恢复现场
        str = str + ')'; //当前位置为')'
        mygen(num, str, ans, cnt + 1);    //递归下一个位置
    }
    vector<string> generateParenthesis(int n) {
        string str;
        vector<string> ans;
        mygen(2 * n, str, ans, 1);
        return ans;
    }
};

###时间复杂度分析 因为序列中的每个位置都会出现(和)两种情况，每个位置都会被计算两次，一共n个位置，总时间复杂度为O(n * 2^n) ###空间复杂度分析 **O(n)**线性的向下递归，故空间复杂度为线性

  • 方法二 递归 + 剪枝 分析：对于方法一可以进一步优化改进复杂度，即可以在枚举括号序列的过程中提前将不合法的序列排除，这样在一个序列前部分已经出现不合法时，不会继续递归。