22. Generate Parentheses

给n对括号，生成所有合规的括号的组合

dfs, 优先添加左括号，当剩余的右括号比左括号多时可以添加右括号，left right分别是剩余的左右括号的数量，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """

        # 5 star, 
        rs = []
        self.helper(n, n, "", rs)
        return rs

    def helper(self, left, right,  path, rs):
        if left == 0 and right == 0:
            rs.append(path)
            return
        if left > 0:
            self.helper(left-1, right, path+"(", rs)
        if right > left:    # 注意这个条件，只有剩余的右括号比左括号多时，才会加右括号
            self.helper(left, right-1, path+")", rs)

todo, go