https://leetcode.com/problems/generate-parentheses/
Generate Parentheses
Total Accepted: 62423 Total Submissions: 186597 Difficulty: Medium
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:
"((()))", "(()())", "(())()", "()(())", "()()()"
Code
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
res = []
def gen(s, left, right, res):
if left:
gen(s+"(", left-1, right, res)
if right > left:
gen(s+")", left, right-1, res)
if not right:
res += [s]
gen("", n, n, res)
return res
Idea
Use recursion to solve this problem. You can also apply this idea to other similar problems, such as print “if else” blocks.
Another variant is that if you know the result of `generateParenthesis(n)` (a list of valid strings), then you can know `generateParenthesis(n+1)` by concatenating “()” in front of all strings in `generateParenthesis(n)`, or add “(” and “)” at the beginning and the end of all strings in `generateParenthesis(n)`.