[LeetCode] 22. Generate Parentheses
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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
用DFS來掃出所有可能性, 關鍵在 第九行 遞迴式的 return.
如果左括號 大於 右括號的數量, 表明這不是一個合法的格式
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
def dfs(l, r, path, res):
print path
if l > r : return
if l == 0 and r == 0: res.append(path)
if l > 0: dfs( l-1, r, path + '(' , res )
if r > 0: dfs( l, r-1, path + ')' , res )
path, res = '', []
if n == 0 : return []
dfs( n, n, path, res )
return res
留言
張貼留言