How do you solve Generate Parentheses on LeetCode?

Generate Parentheses (LeetCode #22) can be solved using Brute Force or Optimal Solution (Backtracking). The optimal approach is Optimal Solution (Backtracking) with O(4^n / sqrt(n)) time complexity and O(n) space complexity. Key insight: The key observation is that for every valid parentheses combination, the number of opening parentheses must always be greater than or equal to the number of closing parentheses at any point in the string.

What is the brute force solution for Generate Parentheses?

The brute force approach for Generate Parentheses is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach generates all possible combinations of parentheses and then filters out the invalid ones. This is similar to trying every possible combination of ingredients to make a dish and then tasting each one to see if it’s good. The optimal Optimal Solution (Backtracking) approach improves this to O(4^n / sqrt(n)).

What algorithm or data structure is used to solve Generate Parentheses?

Generate Parentheses uses the following concepts: String, Dynamic Programming, Backtracking. The recommended patterns to study are: Backtracking, Recursion, Dynamic Programming.

What are the interview tips for Generate Parentheses?

When you first see this problem, clarify the requirements and constraints, and think about how you can represent the parentheses combinations. Communicate your thought process clearly, explaining how you plan to build the combinations and validate them. Mention edge cases, such as the smallest input (n=1) and the largest input (n=8), and how your solution will handle them.

What are common mistakes when solving Generate Parentheses?

Students often forget to check if the number of closing parentheses exceeds the number of opening parentheses during the generation process. Another common mistake is not handling the base case correctly in the recursive function, which can lead to infinite recursion or incorrect results.

#22

Generate Parentheses

Medium

StringDynamic ProgrammingBacktrackingBacktrackingRecursionDynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution (Backtracking)★
Time	O(n²)	O(4^n / sqrt(n))
Space	O(1)	O(n)

💡

Intuition

Time O(4^n / sqrt(n))Space O(n)

The optimal solution uses backtracking to build valid parentheses combinations incrementally. This is like building a wall brick by brick, ensuring at each step that the wall remains stable (valid). If it becomes unstable, we backtrack and try a different configuration.

⚙️

Algorithm

4 steps

1Step 1: Use a recursive function to build the parentheses string, keeping track of the count of opening and closing parentheses used.
2Step 2: If the number of opening parentheses used is less than n, add an opening parenthesis and recurse.
3Step 3: If the number of closing parentheses used is less than the number of opening parentheses, add a closing parenthesis and recurse.
4Step 4: When both counts reach n, add the current string to the results.

solution.py16 lines

1# Full working Python code with comments
2
3def generate_parentheses(n):
4    def backtrack(current, open_count, close_count):
5        if len(current) == 2 * n:
6            result.append(current)
7            return
8        if open_count < n:
9            backtrack(current + '(', open_count + 1, close_count)
10        if close_count < open_count:
11            backtrack(current + ')', open_count, close_count + 1)
12
13    result = []
14    backtrack('', 0, 0)
15    return result
16

ℹ

Complexity note: The time complexity is O(4^n / sqrt(n)) due to the Catalan number which counts the valid combinations of parentheses. The space complexity is O(n) because of the recursion stack.

1The key observation is that for every valid parentheses combination, the number of opening parentheses must always be greater than or equal to the number of closing parentheses at any point in the string.
2Another important insight is to use recursion effectively to build the combinations incrementally, which allows us to avoid generating invalid combinations altogether.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.