赞
踩
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
例如,给出 n = 3,生成结果为:
- [
- "((()))",
- "(()())",
- "(())()",
- "()(())",
- "()()()"
- ]
思路:
回溯+剪枝。
剪枝原则:
放了左括号才能放右括号,left 代表还能放左括号的个数,right 代表还能放右括号的个数。
- class Solution(object):
- def generate(self, temp, left, right, result):
- if (left == 0 and right == 0):
- result.append(temp)
- return
- if (left > 0):
- self.generate(temp + "(", left - 1, right, result)
- if (left < right):
- self.generate(temp + ")", left, right - 1, result)
-
- def generateParenthesis(self, n):
- """
- :type n: int
- :rtype: List[str]
- """
- result = []
- self.generate("", n, n, result)
- return result
-
-
-
-
![](https://csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreWhite.png)
下面写于2019.6.3
- class Solution(object):
- def generateParenthesis(self, n):
- """
- :type n: int
- :rtype: List[str]
- """
- res = []
- def dfs(tmp, left, right):
- if len(tmp) == 2 * n:
- res.append(tmp)
-
- if left:
- dfs(tmp + "(", left - 1, right)
- if right > left:
- dfs(tmp + ")", left, right - 1)
-
- dfs("", n, n)
- return res
![](https://csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreWhite.png)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。