Generate Parentheses

Difficulty: Medium · Topic: Recursion

Given n pairs of parentheses, return all combinations of well-formed parentheses. Any order is accepted.

This is classic backtracking: build the string one bracket at a time, keeping it valid at every step.

Examples

generate_parenthesis(1)
→ ["()"]

generate_parenthesis(2)
→ ["(())","()()"]

generate_parenthesis(3)
→ ["((()))","(()())","(())()","()(())","()()()"]

Target complexity: time O(4ⁿ / √n), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.