Generate Parentheses

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

Generate Parentheses. Given n, list every well-formed string of n pairs of parentheses: each opener gets closed, and no closer comes before its opener.

Say n is three. There are five, from fully nested to three pairs side by side. Five is a Catalan number.

The naive way writes every string of six characters, two choices each: sixty-four strings. Then it checks each one, and throws away fifty-nine. That's four to the n strings, almost all wasted.

Better: build left to right, like a roller coaster track. An opener lays a piece going up, a closer a piece going down. A good ride never dips below the station, and ends back on it. So keep two counters. Add an opener while you have one: open less than n. Add a closer only above the station: close less than open. Every finished track is valid, so nothing is wasted.

In code: when the path has two n pieces, record it. Try an opener: append, recurse, pop. Then try a closer the same way.

With n equal to three: up, up, up, then down, down, down. That's the first ride, fully nested. Now backtrack: pull pieces off until a closer can go where an opener was, and climb again. Dead ends are never built. Five rides, all valid.

The work grows with the Catalan numbers, a bit slower than four to the n. The recursion is two n deep: order n space, plus the output.

Climb while you have pieces, come down only above the station, and keep every ride. That's Generate Parentheses.