22.py

'''
 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:

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

classSolution(object):
defgenerateParenthesis(self, n):
"""
 :type n: int
 :rtype: List[str]
 """

result= []

defbacktracking(S, left, right):
iflen(S) ==2*n:
result.append(S)
return

ifleft<n:
backtracking(S+'(', left+1, right)

ifright<left:
backtracking(S+')', left, right+1)

backtracking('', 0, 0)
returnresult