Problem statement

Given n pairs of parentheses, generate all combinations of well-formed parentheses, in lexicographic order ('(' sorts before ')').

Example 1

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2

Input: n = 1
Output: ["()"]

Constraints

• 1 <= n <= 5

Hints for Generate Parentheses

1. Hint 1

   Track open/close counts: you may add '(' while open < n, and ')' while close < open.

2. Hint 2

   Trying '(' before ')' produces lexicographic order automatically.

How to solve Generate Parentheses

Do not generate all 2^(2n) bracket strings and filter. Instead, only ever build strings that are still capable of being valid: you may add ( while you have opens left, and ) only while there are more opens than closes so far. Every leaf of that search is a valid answer, so nothing is wasted.

Approach

1. Recurse carrying the string built so far plus two counters: open and close, how many of each have been placed.
2. When the string reaches length 2n, it is complete and valid — record it.
3. If open < n, you are allowed another ( — recurse with it.
4. If close < open, there is an unmatched ( waiting, so ) is legal — recurse with it.
5. Try ( before ) at every step.

Why it works

A bracket string is valid exactly when no prefix has more ) than (, and the totals match. The close < open guard enforces the prefix condition at every single step, and the length check enforces the totals, so every string reaching the base case is valid. Conversely any valid string obeys both rules at each character, so the search reaches it. Since ( sorts before ) and is always tried first, the answers come out in lexicographic order without sorting.

Complexity

• Time — O(4^n / sqrt(n))
• Space — O(n)

Pitfalls

• The guard for ) is close < open, not close < n. Using n lets you close a bracket that was never opened.
• Both branches are if, not else if — most states can legally do either, and skipping one loses answers.
• Try ( first if you need lexicographic output; the set is the same either way, but the order is not.

Reference solution

Python

from typing import List

def generateParenthesis(n: int) -> List[str]:
    out = []

    def go(cur, open_count, close_count):
        if len(cur) == 2 * n:
            out.append(cur)
            return
        if open_count < n:
            go(cur + "(", open_count + 1, close_count)
        if close_count < open_count:
            go(cur + ")", open_count, close_count + 1)

    go("", 0, 0)
    return out

Java

public static String[] generateParenthesis(int n) {
    List<String> out = new ArrayList<>();
    goGen(out, "", 0, 0, n);
    return out.toArray(new String[0]);
}

private static void goGen(List<String> out, String cur, int open, int close, int n) {
    if (cur.length() == 2 * n) {
        out.add(cur);
        return;
    }
    if (open < n) goGen(out, cur + "(", open + 1, close, n);
    if (close < open) goGen(out, cur + ")", open, close + 1, n);
}

C++

void goGen(vector<string>& out, string cur, int open, int close, int n) {
    if ((int) cur.size() == 2 * n) {
        out.push_back(cur);
        return;
    }
    if (open < n) goGen(out, cur + "(", open + 1, close, n);
    if (close < open) goGen(out, cur + ")", open, close + 1, n);
}

vector<string> generateParenthesis(int n) {
    vector<string> out;
    goGen(out, "", 0, 0, n);
    return out;
}

JavaScript

var generateParenthesis = function(n) {
    const out = [];
    function go(cur, open, close) {
        if (cur.length === 2 * n) {
            out.push(cur);
            return;
        }
        if (open < n) go(cur + "(", open + 1, close);
        if (close < open) go(cur + ")", open, close + 1);
    }
    go("", 0, 0);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium