Generate Parentheses (LeetCode 22)

The problem

Given n, return every string of n pairs of round brackets that is well-formed: every ( is closed by a later ), and no prefix ever has more ) than (.

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

With two pairs, those are the only balanced strings. ")(()" and "())(" fail because a ) appears before its partner. For n = 3 there are five.

How to think about it

Start with brute force. Generate all 2^(2n) strings of length 2n made of ( and ), then check each with a counter. For n = 3 that’s 64 strings for 5 answers; for n = 10 it’s over a million for 16,796. Almost everything you build is invalid.

The key insight: never build an invalid prefix. A string is balanced exactly when (a) it uses n opens and n closes, and (b) at every point, closes so far ≤ opens so far. Both rules can be checked while you build, one character at a time, using two counters:

• you may add ( if open < n (you still have opens left);
• you may add ) only if close < open (there is an unmatched ( to close).

If you follow these two rules, every string that reaches length 2n is valid. There is nothing to filter at the end, and no dead branch is ever explored.

Which pattern is this? Backtracking with pruning. The tell is “generate all valid strings / arrangements” where validity can be checked on a prefix. Here the “undo” step is free: the code passes s + '(' as a new string, so there’s nothing to pop.

Approach

1. bt(s, open_, close): if len(s) == 2n, record s and return.
2. If open_ < n, recurse with s + '(' and open_ + 1.
3. If close < open_, recurse with s + ')' and close + 1.
4. Start with bt('', 0, 0).

Solution

def generate_parenthesis(n):
    res = []
    def bt(s, open_, close):
        if len(s) == 2 * n: res.append(s); return
        if open_ < n: bt(s + '(', open_ + 1, close)      # an open bracket is still available
        if close < open_: bt(s + ')', open_, close + 1)  # only close what's been opened
    bt('', 0, 0); return res
# generate_parenthesis(3) -> 5 strings ("((()))","(()())","(())()","()(())","()()()")

Dry run

On n = 2, every call in order:

Eight calls, two answers, and not one invalid string was ever built.

Complexity

• Time: O(4ⁿ / √n). The number of answers is the n-th Catalan number, which grows like 4ⁿ / (n^1.5), and each takes O(n) to build. Because no branch is wasted, the work is proportional to the output.
• Space: O(n) for the recursion depth (2n levels), not counting the output.

Edge cases and pitfalls

• n = 1 gives ["()"]. If n = 0 were allowed, the code returns [""].
• Using close < n instead of close < open_ lets you write ) too early and produces invalid strings like "())(".
• Checking validity only at the end works but turns this into the brute force.
• Building with a list is faster for big n: append, recurse, pop. The string version is simpler and fine at interview sizes.

Related problems

• Valid Parentheses (LeetCode 20): checking one string, instead of generating all of them.
• Letter Combinations of a Phone Number (LeetCode 17): another build-a-string backtracking with no undo step.
• Valid Parenthesis String (LeetCode 678): the same open/close counting idea, with wildcards.