22.md

Generate Parentheses

Description

link

---

Solution

此题最重要的地方在于控制不要出现重复，如果简单的用迭代生成左中右三种方法不断回溯，那么必然会出现重复的情况

所以我们可以用右括号大于左的这个特性来做DFS或者递归，一种是使用一个变量open，也可以使用两个变量交替表示，第二种更容易理解

---

Code

O(nlogn)

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []
        def helper(current, n_left, n_right):
            if n_left:
                helper(current+'(', n_left-1, n_right)
            if n_right and n_right > n_left:
                helper(current+')', n_left, n_right-1)
            elif not n_right and not n_left:
                res.append(current)
        helper('', n, n)
        return res

class Solution:
    def generateParenthesis(self, n, open = 0):
        """
        :type n: int
        :rtype: List[str]
        """
        if n == 0:
            return [')'*open]
        if open == 0:
            return ['(' + p for p in self.generateParenthesis(n - 1, 1)]
        else:
            return [')' + p for p in self.generateParenthesis(n, open - 1)] + ['(' + p for p in self.generateParenthesis(n - 1, open + 1)]