Generate Parentheses — Solution

Problem

Given a number n, return every possible string made of exactly n pairs of parentheses where the brackets are properly matched. A string is valid if every opening bracket has a corresponding closing bracket that comes after it, with no orphaned closers.

• Input: n = 3
• Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
• Explanation: There are exactly 5 distinct ways to arrange 3 balanced pairs.

For n = 2 the two valid combinations are ["(())", "()()"]. A string like "())(" is invalid because the second ) has nothing to close.

Intuition

At each position in the growing string you make a binary choice — place ( or ). The insight is that you never need to backtrack and repair a bad string: add ( only while you still have openings left to spend, and add ) only when there is an unmatched ( waiting. Any path through that decision tree that reaches length 2n is valid by construction, so the algorithm produces only correct answers with no filtering step.

Solution — Backtracking

Grow a result string character by character, branching at each step. The two guards (open_count < n and close_count < open_count) ensure every completed string is well-formed.

1. Start with an empty string and two counters tracking how many ( and ) have been placed.
2. If the string length equals 2 * n, record it — the guards guarantee it is valid.
3. If open_count < n, recurse after appending ( and incrementing open_count.
4. If close_count < open_count, recurse after appending ) and incrementing close_count.
5. The two branches are independent; both may execute in the same call.

1def generateParenthesis(self, n: int) -> List[str]:
2    result = []
3
4    def backtrack(current, open_count, close_count):
5        if len(current) == 2 * n:
6            result.append(current)
7            return
8        if open_count < n:              # still have opening brackets to spend
9            backtrack(current + '(', open_count + 1, close_count)
10        if close_count < open_count:    # only close if there's an unmatched open
11            backtrack(current + ')', open_count, close_count + 1)
12
13    backtrack('', 0, 0)
14    return result

Time: O(4^n / √n) — the number of valid combinations is the nth Catalan number; building each takes O(n).
Space: O(n) — the recursion stack goes at most 2n levels deep; output storage is not counted.

Complexity Summary

Common Mistakes

• Adding ) when close_count == open_count — placing a closer when nothing is open produces invalid strings immediately; the guard close_count < open_count prevents this at the source rather than filtering at the end.
• Using a single balance counter instead of two separate counters — a balance counter can tell you whether ) is safe, but it loses the information needed to check open_count < n, which leads to over-generating opening brackets.
• Forgetting to undo the mutable buffer in Java — the StringBuilder is shared across all recursive calls, so omitting deleteCharAt after each branch corrupts every sibling call and produces garbage strings.
• Checking validity only after the string is complete — building the full 2^(2n) candidate space and filtering is orders of magnitude slower; pruning during construction is what makes backtracking efficient here.
• Pre-seeding the string with one ( — starting from ('(', 1, 0) and treating open_count as the remaining budget breaks the symmetry of the two guards and requires awkward off-by-one corrections throughout.

Related Problems

• palindrome-partitioning — backtracking over positions in a string to enumerate all valid segmentations
• letter-combinations-of-a-phone-number — building strings one character at a time by exploring a branching set of choices
• permutations — backtracking to generate every ordering of a fixed set of elements
• subsets — exhaustively exploring include/exclude decisions at each position
• combination-sum-ii — backtracking with early pruning to avoid redundant branches