22. generate parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

solution

This is a classic backtracking problem, very similar to 46-permutations.

def generateParenthesis(self, n: int) -> List[str]:
	ans = []
	def recurse(o, c, acc):
		if o == c and o == n:
			ans.append(acc)
			return
	  
		if o == c:
			recurse(o+1, c, acc+"(")
		elif o > c:
			if o < n:
				recurse(o+1, c, acc+"(")
			recurse(o, c+1, acc+")")
 
	recurse(0, 0, "")
	return ans