力扣(LeetCode)22. 括号生成(C++)

回溯

括号合法的性质：

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

根据性质 ， 写递归体 。

class Solution {
public:
    vector<string> ans;
    vector<string> 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(lc<n) dfs(n,lc+1,rc,path+'(');
        if(rc<n&&lc>rc) dfs(n,lc,rc+1,path+')');
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度 $O(C_{2n}^n)$ ， $n$ 是题目给定的 ， 递归次数等于卡特兰数 $\frac{C_{2n}^n}{n+1}$ ， $push\_back$ 时间复杂度 $O(n)$ ， 二者相乘 ， 时间复杂度 $O(C_{2n}^n)$ 。

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

博主致语

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

AC