回溯

括号合法的性质：

1. 任意前缀的左括号数大于右括号数
2. 左括号和右括号的数量相等。

根据性质 ， 写递归体 。

class Solution {
public:vector ans;vector generateParenthesis(int n) {dfs(n,0,0,"");return ans;}void dfs(int n , int lc,int rc,string path){if(path.size()==2*n) ans.push_back(path);if(lcrc) dfs(n,lc,rc+1,path+')');}
};

时间复杂度 O(C2nn)O(C_{2n}^n)O(C2nn​) ， nnn 是题目给定的 ， 递归次数等于卡特兰数 C2nnn+1\dfrac{C_{2n}^n}{n+1}n+1C2nn​​ ， push_backpush\_backpush_back 时间复杂度 O(n)O(n)O(n) ， 二者相乘 ， 时间复杂度 O(C2nn)O(C_{2n}^n)O(C2nn​) 。

空间复杂度 O(n)O(n)O(n) ， 递归体压栈的最大深度和 pathpathpath 的长度 O(2n)O(2n)O(2n) 相同 ， 空间复杂度 O(n)O(n)O(n) 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC