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)$.

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