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:

1
2
3
4
5
6
7

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

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def generateParenthesis(self, n):
        res = []
        s = [("(", 1, 0)]
        while s:
            x, l, r = s.pop()
            if l - r < 0 or l > n or r > n:
                continue
            if l == n and r == n:
                res.append(x)
            s.append((x+"(", l+1, r))
            s.append((x+")", l, r+1))
        return res

Explaination:

after pop() s= [] x=”(“,l=1,r=0 after append() s = [(‘((‘, 2, 0), (‘()‘, 1, 1)]

after pop() s= [(‘((‘, 2, 0)] x=”()“,l=1,r=1 after append() s = [(‘((‘, 2, 0), (‘()(‘, 2, 1), (‘())‘, 1, 2)]

after pop() s= [(‘((‘, 2, 0), (‘()(‘, 2, 1)] x=”())“,l=1,r=2 (r<l)->continue

after pop() s= [(‘((‘, 2, 0)] x=”()(“,l=2,r=1 after append() s = [(‘((‘, 2, 0), (‘()((‘, 3, 1), (‘()()‘, 2, 2)]

after pop() s= [(‘((‘, 2, 0), (‘()((‘, 3, 1)] x=”()()“,l=2,r=2 ->res.append()

res=[(“()()“)]

after append() s = [(‘((‘, 2, 0), (‘()((‘, 3, 1), (‘()()(‘, 3, 2), (‘()())‘, 2, 3)]

after pop() s= [(‘((‘, 2, 0), (‘()((‘, 3, 1), (‘()()(‘, 3, 2)] x=”()())“,l=2,r=3 (r>n)->continue

after pop() s= [(‘((‘, 2, 0), (‘()((‘, 3, 1)] x=”()()(“,l=3,r=2 (l>n) ->continue

after pop() s= [(‘((‘, 2, 0)] x=”()((“,l=3,r=1 (l>n)->continue

after pop() s= [] x=”((“,l=2,r=0 after append() s = [(‘(((‘, 3, 0), (‘(()‘, 2, 1)]

after pop() s= [(‘(((‘, 3, 0)] x=”(()“,l=2,r=1 after append() s = [(‘(((‘, 3, 0), (‘(()(‘, 3, 1), (‘(())‘, 2, 2)]

after pop() s= [(‘(((‘, 3, 0), (‘(()(‘, 3, 1)] x=”(())“,l=2,r=2 ->res.append()

res=[(“()()“),(“(())“)]

after append() s = [(‘(((‘, 3, 0), (‘(()(‘, 3, 1), (‘(())(‘, 3, 2), (‘(()))‘, 2, 3)]

after pop() s= [(‘(((‘, 3, 0), (‘(()(‘, 3, 1), (‘(())(‘, 3, 2)] x=”(()))“,l=2,r=3 (r>n)->continue

after pop() s= [(‘(((‘, 3, 0), (‘(()(‘, 3, 1)] x=”(())(“,l=3,r=2 (l>n) ->continue

after pop() s= [(‘(((‘, 3, 0)] x=”(()(“,l=3,r=1 (l>n) ->continue

after pop() s= [] x=”(((“,l=3,r=0 (l>n) ->continue

跳出While循环，ruturn res

Note：

初始一个左括号

1. 先加入一个左括号值，再加入一个右括号值（此时最左侧（i=0）为l>r)

2. pop()删除并返回r=-1值，进行判断

   1. l==r==n：res.append()

   2. 再

      （先加入一个左括号值，再加入一个右括号值）

3. 第二步循环，将所有res分量全部append到res中

4. 因为初始一个左括号，加n次左右括号后，左括号数会>n，不断执行pop，将s中置空为止
5. 跳出循环，return res