170. Generate Parentheses

Medium

Topics

Companies

Hint

Open Visualizer

Draw

Input: n = 3

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

Explanation: For n=3, there are 5 well-formed combinations of 3 pairs of parentheses. The function generates all these distinct strings.

Input: n = 1

Output: ["()"]

Explanation: For n=1, there is only one way to form a well-formed pair of parentheses.

Time Complexity

O(4^n / sqrt(n))

Space Complexity

O( (4^n) / (n^(3/2)) * n )