题意

求出所有由n对括号组成的合法括号序列。

思路

我们可以发现，对于一个合法的括号序列，任意一个右括号都一定和前面的一个的左括号配对。因此对于任意一个合法的括号序列，任一时刻其右括号数量一定小于等于左括号。由此，我们可以搜索括号序列并储存所有合法的括号序列，代码如下。

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    int N;
    vector<string> ans;//存储括号序列所用数组
    void dfs(string now,int right,int left)
    {
        if(right == left && right == N) ans.push_back(now);//若括号序列合法。存入答案数组
        if(right < left) return;//若右括号多于左括号，一定不合法，剪枝
        if(right < N) dfs(now+"(",right+1,left);//添加右括号
        if(left < N) dfs(now+")",right,left+1);//添加左括号
    }
    vector<string> generateParenthesis(int n) {
        // write code here
        N=n;
        dfs("",0,0);//开始深搜
        return ans;
    }
};

复杂度分析

时间复杂度：$O(C(2n,n))O(C(2n,n))$,为括号序列的总方案数。

空间复杂度：$O(nC(2n,n))O(nC(2n,n))$,为存储括号序列所用空间。