题目地址：Generate Parentheses - LeetCode
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
这道题目看起来不难，只要把所有的可能性都输出即可。
可以深度优先，或者广度优先解决。
广度优先的Python解法如下，先输出 ()()()...
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def helper(s='', left=0, n=0):
if n == 0:
self.res.append(s+')'*left)
return
if left > 0:
helper(s+')', left-1, n)
helper(s+'(', left+1, n-1)
self.res = []
helper('', 0, n)
return self.res
深度优先解法如下，先 ((()))
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def helper(s='', left=0, n=0):
if n == 0:
self.res.append(s+')'*left)
return
helper(s+'(', left+1, n-1)
if left > 0:
helper(s+')', left-1, n)
self.res = []
helper('', 0, n)
return self.res
文档信息
- 本文作者：last2win
- 本文链接：https://last2win.com/2020/01/24/LeetCode-22.-Generate-Parentheses-Python/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）