Generate parentheses

Given n, return all combinations of n pairs of parentheses that are well-formed.

Before you code

Generating all 2²ⁿ strings and filtering is wasteful. Instead, track how many ( and ) you have placed, and only make choices that keep the prefix valid.

Hints

1. You may add ( while open < n.
2. You may add ) only while close < open: it must close something.
3. Record the string when its length is 2n. Every string you build this way is valid, so nothing is ever thrown away.

Production & complexity notes

When solving Generate parentheses on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Backtracking basics to reinforce the underlying pattern.

What it practices

The choose, explore, unchoose pattern and pruning, from Backtracking basics.