FAANGPrep Sprint

Generate Parentheses

Build only well-formed strings of n pairs, using two guards instead of generating and filtering.

MediumSolve on LeetCode

Examples

Input:n = 3

Output:["((()))","(()())","(())()","()(())","()()()"]

Explain:

The five well-formed strings of three pairs — Catalan(3).

Input:n = 1

Output:["()"]

Explain:

One pair, one way to write it.

Problem Understanding

List every string that uses exactly n opening and n closing parentheses and is well formed, meaning no prefix ever closes more brackets than it has opened.

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

Algorithm Strategy

Instead of generating all 2²ⁿ strings and validating them, we can build only valid strings.

Rules:

Open: We can add an open parenthesis ( if open_count < n.
Close: We can add a closing parenthesis ) if close_count < open_count.

This ensures we never close more than we open (validity) and never exceed n (completeness).

Interactive Visualization

ONE NODE PER CALL · THE LABEL IS THE BRACKET ADDED, BELOW IT: OPENED,CLOSED SO FAR

EMPTY RESULT AND PATH

opened

closed

Answer

—

path (0 of 6)

"" — empty

result

Nothing recorded yet

Start with an empty result and an empty path. 3 pairs, so every answer is 6 characters long

0 opened, fewer than 3 — add "(": the path is (

Every node is one call to backtrack(open, close). Its label is the bracket that call added, and the pair under it is opened, closed — the two counts the guards test. ( branches go left and ) branches go right.

A call with only one child is a guard that said no, and the figure stops on that check as a step of its own: no ( once all n are open, and no ) when there is nothing open to close. The bottom row is the answer, in the order the code returns it.