LeetCode 22. 括号生成

文章目录

题目

22. 括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2:

输入:n = 1
输出:[“()”]

提示:

  • 1 <= n <= 8

思路

算法:
dfs算法 O(n * 22n)

n 对括号一共有 2n 个位置,2n 个位置任意放左括号或者右括号有 22n 种可能。
用二进制数表示每一种情况,某一位为 1 表示放左括号,为 0 表示放右括号,对每一种情况进行分析是否为合法的括号序列。

复杂度:时间复杂度为 O(n * 22n) ,空间复杂度为 O(22n)

代码

C++代码:

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        int i,m=1<<(2*n),j,d=2*n;
        for(i=0;i<m;i++){
            int t=0,l=0,r=0;
            string s="";
            bool f=true;
            for(j=0;j<d;j++){
                if(i>>j&1){
                    t++;
                    l++;
                    s+='(';
                }else{
                    r++;
                    s+=')';
                }
                if(r>l) f=false;
            }
            if(t!=n||!f) continue;
            ans.push_back(s);
        }
        return ans;
    }
};

python3代码:

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        self.dfs(n, n, "", res)
        return res

    def dfs(self, l, r, path, res):
        if l == r == 0:
            res.append(path)
            return
        if l > r or l < 0 or r < 0:
            return
        self.dfs(l - 1, r, path + "(", res)
        self.dfs(l, r - 1, path + ")", res)

相关推荐

  1. LeetCode 22 括号生成

    2024-05-16 13:00:10       32 阅读
  2. [leetcode] 22. 括号生成

    2024-05-16 13:00:10       28 阅读
  3. LeetCode-22.括号生成

    2024-05-16 13:00:10       8 阅读
  4. LeetCode 22. 括号生成

    2024-05-16 13:00:10       6 阅读
  5. leetcode热题HOT 22. 括号生成(回溯)

    2024-05-16 13:00:10       6 阅读

最近更新

  1. .Net Core WebAPI参数的传递方式

    2024-05-16 13:00:10       2 阅读
  2. QT--气泡框的实现

    2024-05-16 13:00:10       3 阅读
  3. LeetCode 968.监控二叉树 (hard)

    2024-05-16 13:00:10       2 阅读
  4. leetcode热题100.完全平方数(动态规划进阶)

    2024-05-16 13:00:10       2 阅读
  5. leetcode328-Odd Even Linked List

    2024-05-16 13:00:10       3 阅读
  6. C 语言设计模式(结构型)

    2024-05-16 13:00:10       2 阅读
  7. v-if 与 v-show(vue3条件渲染)

    2024-05-16 13:00:10       2 阅读
  8. kafka防止消息丢失配置

    2024-05-16 13:00:10       3 阅读

热门阅读

  1. 循环、使用dict和set

    2024-05-16 13:00:10       4 阅读
  2. 使用 Gradle 自定义任务生成初始化 SQL 文件

    2024-05-16 13:00:10       4 阅读
  3. 数学建模(科普)

    2024-05-16 13:00:10       5 阅读
  4. IT行业的现状与未来:技术驱动下的新世界

    2024-05-16 13:00:10       4 阅读
  5. js 数组filter使用

    2024-05-16 13:00:10       5 阅读
  6. RIP、OSPF、BGP等协议及华为路由器配置总结

    2024-05-16 13:00:10       5 阅读
  7. 40-2 了解与安装堡垒机

    2024-05-16 13:00:10       2 阅读
  8. Leetcode 404:左叶子之和

    2024-05-16 13:00:10       3 阅读
  9. 力扣:131. 分割回文串

    2024-05-16 13:00:10       3 阅读
  10. 力扣 72. 编辑距离 python AC

    2024-05-16 13:00:10       4 阅读
  11. 课时126:awk实践_进阶知识_内置函数1

    2024-05-16 13:00:10       4 阅读