aloalgoGenerate Parentheses
Medium
You are given an integer n representing the number of pairs of parentheses.
Your task is to generate all combinations of well-formed (valid) parentheses using exactly n pairs.
Note that:
- A valid parentheses string has every opening parenthesis
(matched with a corresponding closing parenthesis). - At any point in a valid string, the number of closing parentheses must not exceed the number of opening parentheses.
Return all possible valid combinations. The order of the combinations in the result does not matter.
Example 1
Input
3
Output
["((()))", "(()())", "(())()", "()(())", "()()()"]
Explanation:
There are exactly 5 valid combinations using 3 pairs of parentheses.
Example 2
Input
1
Output
["()"]
Explanation:
With only 1 pair, there is exactly one valid combination.
Example 3
Input
2
Output
["(())", "()()"]
Explanation:
With 2 pairs, there are exactly 2 valid combinations.
Input
3
Output
["((()))", "(()())", "(())()", "()(())", "()()()"]