# Generate Parentheses
Given `n`, output all valid combinations of n pairs of parentheses.
## Brute Force
Utilizing a `deque` to generate all possible combinations. The time and space complexity is whopping $O(2^{2n}n)$.
```python
def validate(string):
counter = 0
for p in string:
if p == "(":
counter += 1
else:
counter -= 1
if counter < 0:
return False
return counter == 0
res = []
queue = deque([""])
while queue:
cur_string = queue.popleft()
if len(cur_string) == 2 * n and validate(cur_string):
res.append(cur_string)
continue
queue.append(cur_string + ")")
queue.append(cur_string + "(")
return res
```