首页 > 编程学习 > 力扣(LeetCode)22. 括号生成(C++)

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

发布时间:2022/11/21 1:15:14

回溯

括号合法的性质:

  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+')');
    }
};

时间复杂度 O ( C 2 n n ) O(C_{2n}^n) O(C2nn) n n n 是题目给定的 , 递归次数等于卡特兰数 C 2 n n n + 1 \dfrac{C_{2n}^n}{n+1} n+1C2nn p u s h _ b a c k push\_back push_back 时间复杂度 O ( n ) O(n) O(n) , 二者相乘 , 时间复杂度 O ( C 2 n n ) O(C_{2n}^n) O(C2nn)

空间复杂度 O ( n ) O(n) O(n) , 递归体压栈的最大深度和 p a t h path path 的长度 O ( 2 n ) O(2n) O(2n) 相同 , 空间复杂度 O ( n ) O(n) O(n)

博主致语

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

AC

AC

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式