Yang Shuqi

Generate Parentheses

 

    22. Generate Parentheses

    Solution

    1. As long as open > close in the sequence, the sequence is valid.

    2. In this case we can either append ‘(‘ if we still have open quota, or append ‘)’ if we have more open than close in the sequence.

    3. When close is used up, we have generated all parentheses.

    def generateParenthesis(self, n):
    """
    :type n: int
    :rtype: List[str]
    """
    self.res = []

    def generate(op, cl, s):
        if op > 0:
            generate(op-1, cl, s+'(')
        if cl > op:
            generate(op, cl-1, s+')')
        if cl == 0:
            self.res.append(s)
        return self.res
    
    return generate(n, n, '')
    Search