Generate Parentheses

Generate Parentheses is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Parentheses Generation subpattern.

Problem statement

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

Example 1:

Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1 Output: ["()"]

Constraints:

- 1 <= n <= 8

Topics and companies

Topics: String, Dynamic Programming, Backtracking.

Reported in interviews at Adobe, Amazon, Apple, Bloomberg, ByteDance, Facebook, Google, LinkedIn, Microsoft, Nvidia, Oracle, Uber and others.

How to practise Generate Parentheses on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(4^n / n^(3/2)) ~= Catalan numbers time and O(n) space.

Open Generate Parentheses in the code editor, or read the Generate Parentheses editorial for a worked solution with its approach and complexity analysis.

Where Generate Parentheses sits in the DSA pattern sheet

• Backtracking Patterns pattern guide
• Parentheses Generation subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Generate Parentheses

Other problems that use the same Parentheses Generation and Backtracking Patterns techniques:

• Remove Invalid Parentheses — Hard, same subpattern
• Check if Word Can Be Placed In Crossword — Medium, same pattern
• Combinations — Medium, same pattern
• Combination Sum — Medium, same pattern
• Combination Sum II — Medium, same pattern
• Letter Combinations of a Phone Number — Medium, same pattern