22. Generate Parentheses

Loading...LeetCode

可以发现，结果需要满足两个要求：

1. 含有 n 个左括号和 n 个右括号（必须pair）

2. 必须先出现左括号再出现右括号

根据 2 可以想到，应该是根据状态开关来生成合格结果，f(n) 根据 f(n-1) 来生成，那不是 bfs 就是 dp

12/30/2020 Update:

一看就可以backtracking，既然有左右括号总数限制（都==n），需要 keep track of 已使用的左右括号数量、已经生成的 pattern，测试到 qualified 就直接记录return，没有就继续探索其他。

BFS

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        q = collections.deque([("(", 1, 0)])
        
        while q:
            com, l, r = q.popleft()
            op = l>r
            if len(com) == 2*n:
                res.append(com)
            elif op:
                if l < n: 
                    q.append((com+"(", l+1, r))
                q.append((com+")", l, r+1))
            elif not op and l < n:
                    q.append((com+"(", l+1, r))
        
        return res

Backtracking

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        
        def backtracking(l, r, path):
            if l == 0 and r == 0:
                res.append(path)
                return
            if l > 0:
                backtracking(l-1, r, path+"(")
            if l < r:
                backtracking(l, r-1, path+")")
                
        backtracking(n, n, "")
        
        return res