Generate Parentheses

Given n pairs of parentheses, generate all combinations of well-formed parentheses. Order does not matter.

Why this is worth learning

Validity can be enforced on prefixes. An opening is allowed until n are used; a closing is allowed only when it matches an already unmatched opening.

Before coding: one-minute experiment

With n=3 and prefix (() having open=2 and close=1, which next characters are allowed? Why can a prefix never begin with )?

Function signature

func GenerateParenthesis(n int) []string

Inputs / outputs

• n: number of pairs.
• Return: all valid strings with n pairs of parentheses.

Example

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

Constraints

• 1 <= n <= 8

Core idea (near-solution)

A baseline tries all 2^(2n) strings and validates them. But after a prefix such as ()) fails, no later suffix can repair its earlier unmatched closing parenthesis. Track opens and closes while building instead: their difference is the number of unmatched openings. This state tells whether each next character is legal before its descendants are generated.

Backtrack while tracking how many open and close parentheses you have used. A prefix is valid if closeUsed <= openUsed and openUsed <= n.

Invariant: the current string is always a valid prefix of some well-formed sequence.

Algorithm (step-by-step)

1. DFS with parameters (openUsed, closeUsed, path).
2. If len(path) == 2*n, record it.
3. If openUsed < n, append '(', recurse with one more opening, then restore the previous path length.
4. If closeUsed < openUsed, append ')', recurse with one more closing, then restore the previous path length.

Correctness sketch

Every generated prefix satisfies 0<=close<=open<=n. The opening transition preserves the upper bound, and the closing transition preserves nonnegative balance. At length 2n these inequalities force open=close=n, so every emitted string is balanced. Conversely, every well-formed target string satisfies the same prefix inequalities, so its next character is always one of the permitted branches; following its characters reaches it. Distinct branch sequences produce distinct strings. Restoring the buffer after each branch preserves the parent prefix, and copying on output prevents later writes from changing an answer.

Trace (hand walkthrough)

Example input:
n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Walk:
- build "((()))" by adding 3 opens then 3 closes
- backtrack to produce "(()())", "(())()", "()(())", "()()()"

Pitfalls to avoid

• Allowing closeUsed > openUsed (invalid prefix).
• Forgetting to stop when length reaches 2*n.

Debugging lens

Test every prefix balance, total length 2n, and uniqueness, not merely equal total counts. The string )( has equal totals but fails prefix validity.

Complexity

There are Catalan(n) output strings, each of length 2n. Time O(n Catalan(n)), including copying output, rather than just O(Catalan(n)); auxiliary path and recursion space O(n), excluding output.

Implementation notes (Go)

• Use a []byte buffer and convert to string when recording.

Reconstruction checkpoint

With n=3 and prefix (() having open=2 and close=1, which next characters are allowed? Why can a prefix never begin with )?

Return to Backtracking · Module quiz