What makes parentheses valid?

Think of doors: every door you open must be closed later, and you cannot close a door that was never opened. So a bracket string is valid when two things hold.

First, reading left to right, there are never more closing brackets than opening ones so far. Second, at the end the totals are equal.

Never close early: only add a closing bracket if there is an unclosed opening one.

Limit the openers: only add an opening bracket while you have used fewer than n.

n = 2 · faded branches are pruned: never explored

open: 1
close: 0

At the start, ')' would close something that was never opened. Prune it. Only '(' is allowed.

Move 1 of 5

Pruning the search tree

You could build every string of opens and closes and throw away the bad ones afterwards, but that wastes time. Better to check the rules before each step. If a branch would break a rule, do not go down it at all.

Cutting off a doomed branch early is called pruning. It is like a driver who sees a road is closed and never turns into it. When the string reaches length 2n, it is guaranteed valid.

Pruning: cutting off dead-end branches before exploring them.

Full length: a string of length 2n built this way is always valid.

In code

res, curr = [], []
def go(opens, closes):
    if len(curr) == 2 * n:
        res.append("".join(curr))
        return
    if opens < n:
        curr.append("(")
        go(opens + 1, closes)
        curr.pop()
    if closes < opens:
        curr.append(")")
        go(opens, closes + 1)
        curr.pop()
go(0, 0)
return res