# 22. Generate Parentheses

{% embed url="<https://leetcode.com/problems/generate-parentheses/>" %}

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

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，没有就继续探索其他。

{% tabs %}
{% tab title="BFS" %}

```python
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
```

{% endtab %}

{% tab title="Backtracking" %}

```python
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
```

{% endtab %}
{% endtabs %}
