32. Generate Parentheses

Medium · String

Generate all valid combinations of n pairs of parentheses in sorted order.

You are given a number n representing the number of pairs of parentheses. Your task is to generate every well-formed (valid) combination of n opening and closing parentheses.

A valid combination means: - Every opening parenthesis '(' has a matching closing parenthesis ')' - At no point while reading left-to-right do you have more closing parentheses than opening ones

Return your result as an array of strings, sorted in ascending (lexicographic) order.

Input: n (a positive integer) Output: An array of strings, each representing a valid parentheses combination, sorted ascending

Examples

Example 1
Input: 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Explanation: All 5 valid 3-pair strings

Example 2
Input: 1
Output: ["()"]
Explanation: Only one valid

Constraints

• Standard input/output constraints apply