Generate Parentheses

Problem statement

Given n pairs, return every string of well-formed parentheses. Order in the list does not matter.

Example:

Input:

n = 3

Expected output:

["((()))", "(()())", "(())()", "()(())", "()()()"]

Well-formed means two things: you never have more ) than ( in any prefix, and you finish with the same count of each.

Practice on LeetCode: Generate Parentheses

What we are growing

The string is built one character at a time. At every step you hold a prefix, plus how many opens and closes you have already used.

n = 2 is small enough to draw:

              ""
              |
              (
            /   \
          ((     ()
          |       |
         (()     ()(
          |       |
        (())     ()()

From "(" you may add ( or ). From "((" you may only add ). From "()" you may only add ( — a second ) would make "())", which is already illegal.

You never start with ). Zero opens, so a close is refused.

Why not generate everything

Each of the 2n positions could be ( or ). That is 2^{2n} strings, then a filter. n = 8 is 65,536 candidates, most of them junk like ")))((((".

You do not need those strings. If a prefix is already invalid, every extension of it is invalid. Backtracking refuses the bad prefix, so the junk is never built.

The number of good strings is the Catalan number C_n. The algorithm’s job is to grow only valid prefixes until the length hits 2n.

Golang Solution

A nested generate closes over result. Add ( while leftCount < n. Add ) only while rightCount < leftCount. When len(current) == 2*n, both counters are n, so neither branch fires again — the extra return you might expect is unnecessary.

Time: O(C_n · n) — C_n results, each of length 2n
Space: O(n) — recursion depth, plus the output list

func generateParenthesis(n int) []string {

    var result []string

    var generate func(current string, leftCount, rightCount int)

    generate = func(current string, leftCount, rightCount int) {
        if len(current) == 2*n {
            result = append(result, current)
        }

        if leftCount < n {
            generate(current+"(", leftCount+1, rightCount)
        }
        if rightCount < leftCount {
            generate(current+")", leftCount, rightCount+1)
        }
    }
    generate("", 0, 0)

    return result
}

current+"(" allocates a new string each call. That is fine at interview n (up to 8). A []byte you append and backtrack is the same idea with less copying.