Question
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Plain Text
복사
Example 2:
Input: n = 1
Output: ["()"]
Plain Text
복사
My Answer
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def backtrack(open, close, _str):
if open > n or close >n or open < close:
return
if open == n and close == n:
output.append(_str)
return
backtrack(open +1, close, _str + '(')
backtrack(open, close+1, _str+')')
output = []
backtrack(0,0,'')
return output
Python
복사
Optimized Version
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def dfs(l, r, sub):
if len(sub) == 2 * n:
res.append(''.join(sub))
return
if l < n:
sub.append('(')
dfs(l + 1, r, sub)
sub.pop()
if r < l:
sub.append(')')
dfs(l, r + 1, sub)
sub.pop()
dfs(0, 0, [])
return res
Python
복사
