我要招人

去企业版

首页 > 试题广场 >

括号生成

[编程题]括号生成

热度指数：64941 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。

例如，给出n=3，解集为：

"((()))", "(()())", "(())()", "()()()", "()(())"

数据范围： $0 \le n \le 10$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(2^n)$

示例1

输入

输出

["()"]

示例2

输入

输出

["(())","()()"]

算法知识视频讲解

Python3

lintoon

#使用整对括号插入

class Solution:

def generateParenthesis(self, n: int) -> List[str]:

# write code here

if n == 1:

return ["()"]

ret = []

a = self.generateParenthesis(n - 1)

for i in a:

#根据题目优先从字符串正中间插入整对括号，依次后移，本步有去重功能，但不完全，主要是保证输出的顺序

for j in range(len(i)//2,len(i)+1):

ret.append(i[:j] + "()" + i[j:])

#使用集合去重输出

return list(set(ret))

发表于 2024-04-09 14:55:01 回复(0)

Python3

牛客483061681号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return string字符串一维数组
#
class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        res = []
        
        l,r = n,n
        if n == 1:
            return ["()"]
        
        def bracket(l,r,tmp):
            if r < l:#越界条件，不能先输出），剩余r的数量一定大于l
                return
            if l == 0 and r == 0:#每轮终止条件，剩余lr都为0，则加入到res里
                res.append(tmp)
            if l > 0:
                bracket(l-1,r,tmp + "(")
            if r > 0:
                bracket(l,r-1,tmp + ")")

        bracket(l,r,'')
        return res

发表于 2024-02-20 15:05:52 回复(0)

Python3

对角线1

class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        if n==1:return ["()"]
        lst = []
        for s in self.generateParenthesis(n-1):
            for i in range(len(s)):
                temp = s[:i] + "()" + s[i:]
                lst.append(temp)
        return list(set(lst))

发表于 2023-11-13 22:52:34 回复(0)

Python3

牛客703413254号

想不到答案那种巧妙的办法，只能想到笨办法。。。。。

class Solution:
    def recursion(self, string, res, length):
        tmp = "".join(string)
        if len(string) == length:
            res.add(tmp)
            return res
        
        for i in range(len(string)):
            string.insert(i, ')')
            string.insert(i, '(')
            self.recursion(string, res, length)
            string.pop(i)
            string.pop(i)
        
    def generateParenthesis(self , n):
        # write code here
        length = 2*n
        string = ['(',')']
        res = set()
        self.recursion(string, res, length)
        res = list(res)
        return res

发表于 2023-03-24 18:36:11 回复(0)

Python3

新人帅哥

class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        ans = []
        def dfs(left, right, path):
            if left == right == 0:
                ans.append(path)
                return
            if left > 0:
                dfs(left - 1, right, path + "(")
            if left < right:
                dfs(left, right - 1, path + ")")
        dfs(n, n, "")
        return ans

发表于 2022-11-12 17:09:05 回复(0)

Python3

牛客292060878号

class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        def dfs(l, r, s):
            if l == n and r == n:
                total.append(s)
                return 
            if l <= n:
                dfs(l + 1, r, s + '(')
            if r <= n and l > r:
                dfs(l, r + 1, s + ')')
        total = []
        dfs(0, 0, '')
        return total

思路简单易懂，自行食用

发表于 2022-10-31 11:28:10 回复(0)