22. Generate Parentheses
Given an integer n, build every distinct well-formed string made of exactly n opening and n closing parentheses.
A string is well-formed when every ( is closed by a later ) and no prefix has more ) than (. For n = 3 there are five such strings; in general the count is the n-th Catalan number.
Your function receives n and returns the complete list of valid strings in lexicographic (dictionary) order — note that ( compares smaller than ), so ((())) comes before ()()().
Example 1:
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Explanation: Exactly five balanced arrangements of three pairs exist, listed in dictionary order.
Example 2:
Input: n = 1
Output: ["()"]
Explanation: One pair can only form the single string ().
Constraints:
- 1 ≤ n ≤ 8
Hints:
Think of building the string one character at a time. At any moment, which characters are you still allowed to place?
Track two counts: opens used and closes used. You may add '(' while opens < n, and ')' only while closes < opens — never close more than you've opened.
If you always try '(' before ')' at each step, the recursion emits the strings already in lexicographic order — no sorting needed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 3
Expected output: ["((()))", "(()())", "(())()", "()(())", "()()()"]