Generate Parentheses — Medium Coding Interview Question

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example

Input: n = 3

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

Constraints

• 1 ≤ n ≤ 8

Topics & Companies

Topics: stack, backtracking

Asked by: Amazon, Google, Meta, Microsoft

Optimal Solution Complexity

Time complexity: O(4^n / sqrt(n)). Space complexity: O(n) recursion depth.

Practice more

• All DSA Problems
• DSA Patterns